Binary Search

Binary Search C Implementation      Binary Search C++ Implementation

[Sequential search is simple and easy method. It is efficient for small list of elements but highly inefficient for larger lists. In the worst case we have to make “N” comparisons to search the element]

In binary search a particular item/element with a certain key value say “num” is to be searched. Approximately middle entry of the array is located then it is compared with “num”. if value matches then the search becomes successful otherwise  if middle element is greater then “num” it means the element “num” may be present in first half otherwise it may be present in second half.

After  deciding the half, we will repeat the process till either the element is found or the interval becomes empty.

This method is called binary search because at each step we reduce the length of the array to search by half.(2 parts).

 

We can imagine the efficiency of the binary search by the fact that in just about 20 steps this method can locate an element in a total of 1 million elements.

 Note: Array elements should be sorted (Ascending order)

Algorithm
Binary_search(A,N,NUM)
A :Array containing elements in Ascending order
N :Total elements
NUM: element to search
Step Process
1.   First=0,Last=N-1,Pos=-1
2.   Repeat steps 3 and 4 while (First<=Last and Pos=-1)
3.   Middle=(First+Last)/2
4.   If(A[middle]=num) then
      Pos=middle
      Else
          If(NUM>A[middle]) then
          First=middle+1
          Else
          Last=Middle-1
          [end of if block]
     [end of if block]
5.   If(pos>-1) then
      Pos=pos+1
      Display pos
      Else
      Display “element is not present”
      [end of if block]
6.   Return

Complexity

The complexity is measured by the number of comparisons to locate the element in the array. Each comparison reduces the array size to search by half. Thus the maximum number of key comparisons is approximately 2*log2n as two key comparisons are made each time through the loop.
The running time for the worst case is approximately equal to log2n.
The running time for the average case is approximately equal to the running time for the worst case.

Binary Search C Implementation      Binary Search C++ Implementation

Number Of Visitors

0125549