If we have ‘n’ records which have been ordered by keys so that x1 < x2 < … < xn . When we are given a element ‘x’, binary search is used to find the corresponding element from the list. In case ‘x’ is present, we have to determine a value ‘j’ such that a[j] = x (successful search). If ‘x’ is not in the list then j is to set to zero (un successful search).

In Binary search we jump into the middle of the file, where we find key a[mid], and compare ‘x’ with a[mid]. If x = a[mid] then the desired record has been found. If x < a[mid] then ‘x’ must be in that portion of the file that precedes a[mid]. Similarly, if a[mid] > x, then further search is only necessary in that part of the file which follows a[mid].

If we use recursive procedure of finding the middle key a[mid] of the un-searched portion of a file, then every un-successful comparison of ‘x’ with a[mid] will eliminate roughly half the un-searched portion from consideration.

Since the array size is roughly halved after each comparison between ‘x’ and a[mid], and since an array of length ‘n’ can be halved only about times before reaching a trivial length, the** worst case complexity of Binary search is about .**

**Time Complexity:**

The time complexity of binary search in a successful search is **O(log n)** and for an unsuccessful search is **O(log n).**

You may be interested in:

Data Structures and Algorithms – MCQs.

Data Structures and Algorithms Online Tests