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.
ComplexityBest caseAverage caseWorst case
TimeO(1)O(log n)O(log n)
Space  O(1)
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  

Output

enter the search element
35
element index value is 4

Pin It on Pinterest

Share This