Binary Search

Facebooktwitterredditpinterestlinkedinmailby feather

When there is a large data structure, the linear search takes a lot of time to search the element. The binary search was developed to overcome the lack of a linear search. It is based on the divide & conquers principle. It is a very fast searching algorithm. The time complexity of the binary search is O (log n). A binary search can only be applied to a sorted list.

In this searching technique, the given element is compared with the middle element of the list.

  • If both elements are equal, it returns the index value.
  • If both elements are not equal, we check whether the given element is larger or smaller than the middle element.
  • If the given element is smaller than the middle element, we will repeat the same process in the smaller part of the list.
  • If the given element is larger than the middle element, we will repeat the same process in the larger part of the list.

Complexity of Binary search

Complexity Best case Average case Worst case
Time O(1) O(log n) O(log n)
Space     O(1)

Algorithm of Binary search

Binary_Search( ) Step 1: SET BEG = lower_bound, END = upper_bound, FLAG = – 1 Step 2: Repeat Steps 3 and 4 while BEG <=END Step 3: SET MID = (BEG + END)/2 Step 4: if A[MID] = VAL
             SET FLAG = MID
             print “index value of the element”
             Go to Step 6
             else if A[MID] > VAL
             else END = MID – 1
             else
             SET BEG = MID + 1
             // end of if
             // end of loop Step 5: if FLAG = -1
             print ” element is not found in this list “
             // end of if Step 6: exit  

For example, suppose you have the following array, and you have to search 30 in it.

Iteration 1: BEG = 0                     END = 8                     MID = (BEG + END) / 2                                 (0 + 8) / 2 = 4                     A[MID] = VAL                     A[4] = 30                     35 ≠ 30         // not equal           Iteration 2: BEG = 0                     END = MID – 1                              = 4 – 1 = 3                     MID = (0 + 3) / 2                              = 1                     A[1] = VAL                     27 ≠ 30         // not equal   Iteration 3: BEG = MID + 1                              = 1 + 1                              = 2                     END = 3                     MID = (2 + 3) / 2                              = 2                      A[2] = VAL                      29 ≠ 30         // not equal Iteration 4: BEG = MID + 1                              = 2 + 1                              = 3                     END = 3                     MID = (3 + 3) / 2                              = 6                     A(3) = VAL                       30 = 30            // equal                                        Index value of 32 is 3.

Binary search program in C language  

#include<stdio.h>   int binarySearch(int[], int, int, int);   void main ()   {       int arr[10] = {6,  9, 12, 23, 35, 46, 68, 90, 96, 120};       int item, location=-1;        printf(“enter the search element “);       scanf(“%d”,&item);       location = binarySearch(arr, 0, 9, item);       if(location != -1)        {           printf(“element index value is %d”,location);       }       else       {           printf(“element not found”);       }   }    int binarySearch(int a[], int beg, int end, int item)   {       int mid;       if(end >= beg)        {              mid = (beg + end)/2;           if(a[mid] == item)           {               return mid+1;           }           else if(a[mid] < item)            {               return binarySearch(a,mid+1,end,item);           }           else            {               return binarySearch(a,beg,mid-1,item);           }             }       return -1;    }    

Output

enter the search element 35 element index value is 4
Facebooktwitterredditpinterestlinkedinmailby feather