Binary search algorithm in data structure with explanation

by

Binary search is a very efficient searching technique for finding an element from a sorted Array. This technique follows the divide and conquers approach to perform a searching operation.

Suppose we have 10,000 sorted elements in an array and want to search a value in that array. If we follow linear searching, then in the worst case, we have to compare search value with all 10,000 elements in the list.

But when we use binary search, we need only log n base two comparison means 14 comparisons only in the worst case. So you can see how binary search is efficient for more massive data in comparison to the linear searching technique.

Binary search is also known as a half-interval search and logarithmic search in computer science.

In this technique, we first find the middle element from the sorted array, and then we break it into two half parts and then compare the search value with the middle element.

  • If the search value is equal to the middle value, then return the middle-value index means search value found in the middle.
  • If the search value is greater than the middle value, then the next search will only be done on the second half array.
  • If the search value is smaller than the middle value, then the next search will be done in the first half of the array.
  • And if the search value is not found anywhere, it will return -1 or any message like “no item found”.

Binary search algorithm

Step 1. Start with a sorted array
Step 2. Find the middle element and divide it into two-part.
Step 3. Compare the search value with the middle element if match found, then return the middle index. If not, then follow step 4 and step 5 accordingly.
Step 4. If the search value is greater than the middle, then select the right part of the array after division and follow step 2
Step 5. If the search value is lesser than the middle, then select the left part of the array after division and follow step 2
Step 6. When a match is found, then return the index of the element.
Step 7. If no match is found, then return -1.

function binary_search(K, n, X) is
    L = 0
    R = n − 1
    while L ≤ R do
        m = round((L + R) / 2)
        if K[m] < X then
            L = m + 1
        else if K[m] > X then
            R = m − 1
        else:
            return m
    return -1

Binary search time complexity

Worst-case performance O(log n)
Best-case performance O(1)
Average performance O(log n)
Worst-case space complexity O(1)

Simple binary search program in C

#include &lt;stdio.h&gt;
int main()
{
  int first, last, middle, n, i, value, arr[500];

  printf("Elements you want in array (less than 500): \n");
  scanf("%d", &amp;n);

  printf("Please Enter %d integer value:\n", n);

  for (i = 0; i &lt; n; i++)
    scanf("%d", &amp;arr[i]);

  printf("Please enter search value: \n");
  scanf("%d", &amp;value);

  first = 0;
  last = n - 1;
  middle = (first+last)/2;

  while (first &lt;= last) {
    if (arr[middle] &lt; value){
      first = middle + 1;
    }
    else if (arr[middle] == value) {
      printf("%d found at array index %d.\n", value, middle);
      break;
    }
    else{
      last = middle - 1;  
    }
    middle = (first + last)/2;
  }
  if (first &gt; last){
    printf("%d isn't present in the list.\n", value);
  }
  return 0;
}

Output:

[wpusb]