Binary search (6)
Analysis (counting comparisons):
Let n be the length of the array.Assume that steps 2.2–4 perform a single comparison.
If the search is unsuccessful, these steps are repeated as often as we must halve n to reach 0:
No. of comparisons = floor(log2 n) + 1
If the search is successful, these steps are repeated at most that many times:
Max. no. of comparisons = floor(log2 n) + 1
In either case, the time complexity is O(log n).