How do you implement binary search algorithm? What is time complexity of this algorithm?

Question

Suresh Chand · Accepted Answer

Binary search is an extremely efficient search technique that searches the given item in minimum possible comparisons in the already sorted list of given elements. The logic behind the technique is: First find the middle element of the list Compare the mid-element with searched item.     There are three cases: If it is a desired element then search is successful. If it is less than desired item then search only in the first half of the list. If it is greater than desired item then search in the second half of the list. Recursive Algorithm: BinarySearch(A,l,r, key) { if(l= = r) { if(key = = A[l]) return l+1; //index starts from 0 else return 0; } else { m = (l + r) /2 ; if(key = = A[m]) return m+1; else if (key < A[m]) return BinarySearch(l, m-1, key) ; else return BinarySearch(m+1, r, key) ; } } Example: Consider an array of data:  21, 36, 56, 79, 101, 123, 142, 203 Now, Tracing binary search for above data; 21 36 56 79 101 123 142 203 0 1 2 3 4 5 6 7 Set L=0, R=7, key=123 (search for 123) S.No. L R Mid=(L+R)/2 Remarks 1. 2. 0 4 7 7 (0+7)/2=3 (4+7)/2=5 Key>a[3] Key==a[5] Therefore, search successful and key(123) is at position (Mid+1)=5+1=6. Efficiency: From the above algorithm we can say that the running time of the algorithm is T(n) = T(n/2) + O(1)         = O(logn) In the best case output is obtained at one run i.e. O(1) time if the key is at middle. In the worst case the output is at the end of the array so running time is O(logn) time. In the average case also running time is O(logn).

How do you implement binary search algorithm? What is time complexity of this algorithm?

Leave your Answer:

Hits Counter

Question

How do you implement binary search algorithm? What is time complexity of this algorithm?

Leave your Answer: