# Understanding binary search

Suppose, `numbers` is a `list/array` of integers that are sorted in nondecreasing order. We need to determine whether an element `x` is present in the `list` or not. There are `n` elements in the `list` .

### Linear search

Before using `binary search` let’s check how linear search will perform in this problem.

Let’s, n = 10⁶ ( here,`numbers` is a list of 10⁶ integers).
If x is present at the first position of the `list` then we will get our expected result at the first iteration. This will work in `O(1) `time. Pretty fast! NO?

But if x is present at 10⁶th position(or not present in the list) then it will take `O(n)` time to calculate the result and if we search for n times then time complexity will be` O(n²)`, pretty slow, NO?

So we can say that, at worst case linear search will work in `O(n²)` time complexity (for n number of elements and n number of searches).

Here `binary search` will do the trick!

### Binary Search

Binary search works using divide-and-conquer approach. At every iteration it breaks the original problem into sub-problems and solution of sub-problems will be solution of original problem. Interesting, YES?

Every time `binary search` divides the original search space into two equal sized search space (depending of implementation logic it may change).

With the help of knowledge of logarithm we can guess that binary search will take at most log2(10⁶) = 19.93 ~20 iterations for this problem (where linear search may take at most 10⁶ iterations!). Notice better the performance!

#### Iterative approach

Following code snippets are iterative approach of binary search :

Python code :

Javascript code :

#### Recursive approach

Following code snippets are recursive approach of binary search :

NOTE : For recursive approach conditions of breaking the recursion should be appeared first, otherwise you may fall in infinite loop!

Python code :

• * Can you guess why return `x == numbers[high]` will work also?

Javascript code :

### More optimization (variation of binary search) :

Find the differences between previous codes the the following iterative ones :

Python code :

Javascript code :

Notice, we’ve less comparisons here (can you find which ones?). This will improve performance significantly.

Now, look at line 8, we’ve used `high=n` (not `n-1`, high is one more than the highest possible index). If we used `high=n-1` then it would work instead of some corner cases. If our expected element is the last element and `high=n-1` then `low` will never be able to point the last element.

For example, call the optimized `binary_search` function using the following data (once using high=n-1 and then using high=n), this will clear the scenario.
`numbers = [1, 2, 3, 4, 5]n = 5x = 5`

Additional Note : Instead of `return x == numbers[low]` we can write:

### Comparison to linear search :

At worst case, for n number of elements and n number of searches linear search will have `O(n²)` time complexity.
For sorted numbers, binary search will have `O(nlogn)` complexity [for n number of searches].
If the numbers are not previously sorted then we can use `quick sort` or `merge sort` algorithms (both of them have `O(nlogn)` time complexity) and then apply binary search.

In this case,
Total worst case time complexity = Worst case time complexity of sorting (let merge sort) + worst case time complexity of binary search
= `O(nlogn)`+`O(nlogn)`
= `2*O(nlogn)`
~`O(nlogn)`
We can decide that, if the numbers are not sorted, still `binary search` will perform better than `linear search`!

# More by Taohidul Islam Topics of interest