What is Binary Search? Explain Binary Search with C source code. Is this more efficient than Linear Search?

Binary Search array elements

Binary search sorts the records either in ascending or descending order to gain much better performance than linear search. This can alternatively insert a new element in the list so that it remains in sorted order. Which ever may be the approach, either populating the list and then do the sorting or populate the list in sorted order, we always get a sorted list before doing the binary search. Now suppose we have an ascending order record. At the time of search it takes the middle record/element, if the searching element is greater than middle element then the element mush be located in the second part else it is in the first half. In this way this search algorithm divides the records in the two parts in each iteration and thus called binary search.

Binary Search algorithm

A technique for searching an ordered list in which it first checks the middle item and based on that comparison it discards the other half the records. The same procedure is then applied to the remaining half until a match is found or there are no more items left.

In binary search, we first compare the key with the item in the middle position of the array. If there's a match, we can return immediately. If the key is less than the middle key, then the item must lie in the lower half of the array; if it's greater then the item must lie in the upper half of the array. So we repeat the procedure on the lower or upper half of the array depending on the comparison. (See following diagram) Each step of the algorithm divides the block of items being searched in half. We can divide a set of n items in half at most log2 n times. Thus the running time of a binary search is proportional to log n and we say this is a O(log n) algorithm.

The following example code shows how to search records with binary search and also how efficient it is than linear search.

Binary Search using array

int binary_search(int low_indx, int high_indx, 
                  int record[], int record_val)
{
  int mid, mid_val;
  static int iteration, last_mid_val = -1;
  mid = (high_indx + low_indx) /2;
  if(high_indx > low_indx && record)
  {
    mid_val = record[mid];
    if(last_mid_val == mid_val)
    {
      return mid;
    }
    last_mid_val = mid_val;
    printf("Iteration %d middle index %d, value %d\n", 
      iteration++, mid, mid_val);
    if(mid_val == record_val)
    {
      return mid;
    }
    else if(record_val > mid_val)
    {
      return binary_search(mid, high_indx, record, record_val);
    }
    else
    {
      return binary_search(low_indx, mid, record, record_val);
    }
  }
  else
  {
    return -1;
  }
}
int linear_search(int low_indx, int high_indx, 
                  int record[], int record_val)
{
  int index;
  for(index = low_indx; index < high_indx; index++)
  {
    printf("Iteration %d \n",index);
    if(record[index] == record_val)
    {
      return index;
    }
  }
  return -1;

}
int main(int argc, char *argv[])
{
  int records[20] =
  {
    0, 3, 6, 7, 8, 9, 10, 13, 14, 16,
    19, 20, 25, 27, 29, 31, 32, 38, 40, 41
  };
  int record_index, record;
  printf("Search element:");
  scanf("%d", &record);
  printf("\nLinear Search\n");
  record_index = linear_search(0, 20, records, record);

  if(record_index == -1)
  {
    printf("Record not found!");
  }
  else
  {
      printf("Record index %d", record_index);
  }
  printf("\nBinary Search\n");
  record_index = binary_search(0, 20, records, record);

  if(record_index == -1)
  {
    printf("Record not found!");
  }
  else
  {
    if(records[record_index] == record)
    {
      printf("Record index %d", record_index);
    }
    else
    {
      printf("Record not found!");
    }
  }
  return 0;
}

Binary Search program vs linear search program

Search element:25

Linear Search
Iteration 0
Iteration 1
Iteration 2
Iteration 3
Iteration 4
Iteration 5
Iteration 6
Iteration 7
Iteration 8
Iteration 9
Iteration 10
Iteration 11
Iteration 12
Record index 12

Binary Search
Iteration 0 middle index 10, value 19
Iteration 1 middle index 15, value 31
Iteration 2 middle index 12, value 25
Record index 12

Analysis: Binary search requires a more complex program than linear search and thus for small n it may run slower. This graph shows how f(n) value increments with the value of n linearly but log(n) value at startup is greater than n but slowly at higher values of n is is much smaller than n.

Mathematically, for large n, log(n) is much larger than n. Thus ratio of log(n):n tends to become zero.

We can say that when number of records n will be very high binary search will give the result much faster than linear search O(n).

Points to remember:

• Linear search do not require list to be ordered.
• Binary search always require the list of records to be ordered.
• Before performing binary search unordered list should be sorted for once.
• It is also possible to insert each item in a manner so that list becomes automatically sorted at the time of insertion.
• Linear search is very good and efficient when number of records are less like few hundreds.
• In embedded system and small size system dealing with less number of records, always choose linear search.
• Binary search is a bit complex, uses recursion and needs more resources like stack memory. It is well suited for system dealing with very larger number of records.
• Binary search is very often used in database servers.

About our authors: Team EQA

You have viewed 1 page out of 252. Your C learning is 0.00% complete. Login to check your learning progress.

‹ # ›