Question

Question 5
Write a program to find the number of comparisons using binarySearch and the sequential search algorithm as follows:
Suppose list is an array of 1000 elements.
5.1 Use a random number generator to fill list.
5.2 Use any sorting algorithm to sort list.
5.3 Search list for some items as follows:
a. Use the binary search algorithm to search the list. (You may need to modify the algorithm given in this chapter to count the number of comparisons.)
b. Use the binary search algorithm to search the list, switching to a sequentialsearch when the size of the search list reduces to less than 15. (Use the sequential search algorithm for a sorted list.)
Print the number of comparisons for Questions 5.3a and b. If the item is found in the list, then print its position.

Answer 1

Hi

I have written the code for above functions and tested it and its working fine, kindly check and let me know if you have any issues.

#include "stdafx.h"
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define LIST_CNT 1000

int listArr[LIST_CNT];
int comparisionCnt = 0;

int binarySearch(int *ptr, int l, int r, int item)
{
   while (l <= r) {
       int m = l + (r - l) / 2;
       // Check if item is present at mid
       if (ptr[m] == item) {
           return m;
       }
       else {
           comparisionCnt++;
       }
       // If item greater, ignore left half
       if (ptr[m] < item)
           l = m + 1;
       // If item is smaller, ignore right half
       else
           r = m - 1;
   }
   // if we reach here, then element was
   // not present
   return -1;
}

int binarySearchAndLinearSearch(int *ptr, int l, int r, int item)
{
   char seqSearch = 0;
   int m;
   while (l <= r) {
       m = l + (r - l) / 2;
       if ((LIST_CNT - m) < 15) {
           seqSearch = 1;
           break;
       }
       // Check if item is present at mid
       if (ptr[m] == item) {
           return m;
       }
       else {
           comparisionCnt++;
       }
       // If item greater, ignore left half
       if (ptr[m] < item)
           l = m + 1;
       // If item is smaller, ignore right half
       else
           r = m - 1;
   }
   for (int i = m;i < LIST_CNT;i++) {
       if (ptr[m] == item) {
           comparisionCnt++;
           return m;
       }
   }
   // if we reach here, then element was
   // not present
   return -1;
}
void mySort(int *ptr, int cnt) {

   for (int i = 0; i<cnt;i++) {
       for (int j = i + 1;j < cnt;j++) {
           int tmp;
           if (ptr[i] > ptr[j]) {
               tmp = ptr[i];
               ptr[i] = ptr[j];
               ptr[j] = tmp;
           }
       }
      
   }

}

int main()
{
   //initialize array list
   for (int i = 0;i < LIST_CNT;i++) {
       listArr[i] = rand();
   }
   printf("Before Sorting list \n");
   for (int i = 0;i < LIST_CNT;i++) {
       printf("%d ",listArr[i]);
   }
   mySort(listArr, LIST_CNT);
   printf("After Sorting list \n");
   for (int i = 0;i < LIST_CNT;i++) {
       printf("%d ", listArr[i]);
   }

   comparisionCnt = 0;
   int index = binarySearch(listArr, 0, LIST_CNT - 1, 32678);
   printf("\n Binary Search index of item = %d comparision count = %d \n", index,comparisionCnt);
  
   comparisionCnt = 0;
   index = binarySearchAndLinearSearch(listArr, 0, LIST_CNT - 1, 32678);
   printf("\n Binary Search and linear search index of item = %d comparision count = %d \n", index, comparisionCnt);

   getchar();
   return 0;
}