Binary Search

Explanation and different use cases of Binary Search.

Binary Search operates on a contiguous sequence with a specified left and right index. This is called the Search Space. Binary Search maintains the left, right, and middle indices of the search space and compares the search target to the middle value of the collection.

Time and Space Complexity:

Runtime: O(log n)

Because Binary Search operates by applying a condition to the value in the middle of our search space and thus cutting the search space in half, in the worse case, we will have to make O(log n) comparisons, where n is the number of elements in our collection.

Why log n?

• Binary search is performed by dividing the existing array in half.

• So every time we complete one iteration the size reduced to half of the existing part.

• First N become N/2, then it become N/4 and go on till it find the element or size become 1.

• The maximum no of iterations is log N (base 2).

Space Complexity: O(1) -- Constant Space

Different problems of binary search:

page1.Search in a Sorted Rotated Arraypage2.Find Minimum in Rotated Sorted Arraypage3.Find Peak Elementpage4. Find First and Last Position of Element in Sorted Arraypage5.Sqrt(x)