Binary Search

Assume that I am going to give you a book. This time the book will have ordered page numbers unlike previous scenario (Linear search) .

Example

First page number as 1,

Second page number as 2,

And so on.

What will you do if you ask to find page number 67.

Since the page numbers are ordered in ascending, we can do something like below,

1.Open the center page of the book.

2.if the page number is equal to 67. We are done

Otherwise,

3.if

The page number is less than 67. (say 62)

You can leave the left part of the book which will have the page number from 1 to 62.

Follow the step 1 with the right part of the book. In this case starting page will be 63 (center + 1)

4.else

The page number is greater than 67. (say 75)

You can leave the right part of the book which will have the page number from 75 to end of the book.

Follow step 1 with the left part of the book. In this case ending page will be 74 (center - 1)

5.Do the above process until we find page number 67 or run out of page.

Binary Search: Found Case

Binary Search Found

Binary Search: Not Found Case

Binary Search Not Found

Here every time we are deciding either select left side or right side. Hence, it is called as binary search.

If we want to do binary search, the array should be in sorted order.



Binary Search Program in c

Example

/*
 * Program:  Binary Search
 * Language: C
 */

#include<stdio.h>

//size of the array
#define SIZE 8 

/*
 * It will return 1, if search found
 * Otherwise it will return 0
 */

int BinarySearch(int arr[],int start, int end, int key)
{
  int mid;

  //do till valid range
  while(start <= end)
  {
      //find mid index
      mid = (start + end) / 2;

      //if arr[mid] is equal to key, search found
      if(arr[mid] == key)
       return 1;

      /*
       * if key is greater than arr[mid], skip left side array.
       * move the starting position to mid + 1 index
       */
      if(arr[mid] < key)
       start = mid + 1;
      else
      /*
       * skip right side array.
       * move end position to mid - 1 index
       */
       end = mid - 1;

  }

  /*
   * Out of the loop
   * Which means Key not present in the array, so return 0.
   */
  return 0;
}

int main()
{
  //sorted array
  int page_number[SIZE] = {10,23,45,70,90,100,111,123};

  //search found case
  int key = 45;

  if(BinarySearch(page_number,0,SIZE - 1, key) == 1)
      printf("Search Found\n");
  else
      printf("Search Not Found\n");

  //search not found case
  key = 150;

  if(BinarySearch(page_number,0,SIZE - 1, key) == 1)
      printf("Search Found\n");
  else
      printf("Search Not Found\n");

  return 0;
}



Visual Representation of Binary Search

Binary Search


Time Complexity of Binary Search (worst case)

Binary search worst case analysis