# Binary Search

by 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 = 30                     35 ≠ 30         // not equal           Iteration 2: BEG = 0                     END = MID – 1                              = 4 – 1 = 3                     MID = (0 + 3) / 2                              = 1                     A = VAL                     27 ≠ 30         // not equal   Iteration 3: BEG = MID + 1                              = 1 + 1                              = 2                     END = 3                     MID = (2 + 3) / 2                              = 2                      A = 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   int binarySearch(int[], int, int, int);   void main ()   {       int arr = {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
by 