[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.
