Binary Search


Binary Search is a searching algorithm in which the element is to be searched from a given sorted array. We take benefits of the array being sorted already. During the search for desired element, half of the elements are eliminated at every step.

Binary Search is one of the most important Algorithm in competitve programming. Many interview questions have solutions including this binary search. The facts that makes it so essential are efficiency and less time hence faster than Linear Search.

Algorithm for Binary Search

Statement: Find a given element x from the sorted array.
Step 1: Divide array into three parts, left half, right half and the middle element.
Step 2: Check if the middle element is x and return it.
Step 3: If its not the middle element, then compare given element with middle,
if element > middle => start = mid
if element < middle=> end = middle.
Step 4: Repeat above steps till we find the elementin any intermediate mid position, or array reduces to size 1 i.e. start=end.

Code:



Tips and Tricks

While calculating middle index, we simply do
mid = (start+end)/2
But the problem here is, if the start and end are both too long, say comparable to range of integer i.e. 10^9 and you are coding in C,C++ or Java,etc then addition of such large numbers can overflow integer and calculation will be wrong.
For example, suppose, we can store maximum number '5' in side a integer variable(actual is 10^9). Both start and end are high values like 3 and 4 respectively.
(start+end) = 3+4 = 7
But as discussed, our integer can hold only upto 5 maximum. So the number will overflow and a garbage will be stored or 2 will be stored.
    Numbers: 1  2  3  4  5  6  7
    Storage: 1  2  3  4  5  1  2
To avoid above scenario, we use the formula,
mid = start + (end-start)/2
This will avoid the overflowing of range of integer.

Another thing is we have to always return the index, keep that in mind. I myself sometimes returns somthing like arr[mid], whereas I should have returned only mid. This is just a small tip from me.

Advantages

1. Time complexity is (log2n)
2. Less no of comparisions compared to linear search
3. Array is sorted (also a disadvantage)

Disadvantages

1. The array should be sorted is the major limitation
2. It's more complicated than Linear search
3. Not always feasible for arrays which would be growing continuously

Binary Search is a very important algorithm and many questions in coding interviews, competitve programming, hackathon problems, coding exams,etc have the implementation of it at some or the other point.