Everything about BINARY_SEARCH

Binary Search is a typical searching technique utilized in computer science throughout the long term. This is a pursuit calculation that requests all the components to be sorted first. In 1960 Derrick Henry Lehman distributed a parallel hunt calculation that worked in all PC exhibits.

Binary Search follows the Divide and Conquer strategy to overcome the disadvantage of Liner Search Algorithm which involves iterating over all the elements until the target element is found. Binary Search took down Linear Search by its O(log2 n) running time which is lesser than O(n) time. Here n is the number of elements in the array.

Binary Search

Algorithm

Here N is the length of the sorted array and k is the element to be found.

low = 0
high = N-1
loop while low <= high
    middle = low+(high-low)/2
    if array[middle] == k
    return middle
    else if array[middle] < k
    low = middle+1
    else 
    high = middle-1
End loop
return Not Found 

Example of Binary Search

From our Above Example, We can see that Binary Search is far better than Linear Search.

In the worst case, Binary Search needs log2(n)+1 iterations which are far better than O(n).

Consider we have 999 elements in an array of size 1000 numbers starting 1 to 999. we have to find the number 750. Linear Search takes 749 iterations to find the target element where Binary Search needs only 2 iterations.

if an iteration takes 1 msec(millisecond) then Linear Search takes 749 msec where Binary Search takes just 2 msec.

Binary Search Implementation

Complexity Analysis

Time Complexity :

Time Complexity says how much time your program has taken to complete the process. Let's consider n is the length of the sorted array.

Iteration 1:
length of array = n.
Iteration 2:
length of array = n/2.
Iteration 3:
length of array = (n/2)/2.
.
.
.
Iteration k:
length of array = (n/2)^k.
After k divisions, the length of the array becomes 1.
so,
1 = (n/2)^k.
n = 2^k.
Take base-2 Logarithm on both sides.
log2 (n) = log2 (2^k).
As per Logorithmic properties.
log2(n) = k log2 (2).
Therefore,
log2 (n) = k  [logA (A) = 1].

Above, we successfully derived the time complexity of the Binary Search Algorithm.

Space Complexity:

Space Complexity says how much memory or other computer resources has been taken by your program to complete the process.

Here Binary Search requires zero extra space. so, the space complexity of our algorithm is O(1) constant space.

Running Time and Cache usage

In analyzing the performance of binary search, another consideration is the time required to compare two elements. For integers and strings, the time required increases linearly as the encoding length (usually the number of bits) of the elements increase. For example, comparing a pair of 64-bit unsigned integers would require comparing up to double the bits as comparing a pair of 32-bit unsigned integers.

The worst case is achieved when the integers are equal. This can be significant when the encoding lengths of the elements are large, such as with large integer types or long strings, which makes comparing elements expensive. Furthermore, comparing floating-point values (the most common digital representation of real numbers) is often more expensive than comparing integers or short strings.

Duplicate Elements

Consider our array contains duplicate copies of target element k. In this scenario, we can’t conclude that our algorithm always returns the first occurrence of the target element. It may return the second/last occurrence of the target element also.

So that we have to say whether our algorithm has to return the first or the last occurrence of the target element.

We can return the leftmost occurrence :

function binary_search_leftmost(A, n, T):
    L := 0
    R := n
    while L < R:
        m := floor((L + R) / 2)
        if A[m] < T:
            L := m + 1
        else:
            R := m
    return L

or the rightmost occurrence :

function binary_search_rightmost(A, n, T):
    L := 0
    R := n
    while L < R:
        m := floor((L + R) / 2)
        if A[m] > T:
            R := m
        else:
            L := m + 1
    return R - 1

Here L = left/low, R = right/high, m=middle.

Consider this example: [4, 5, 5, 7, 8, 8, 8, 8, 9, 9]. You have to find the range of integer 8, that you have to return [4, 8] as output. Let’s design our Algorithm. We can have a boolean variable to say whether we are looking for the first occurrence of the element or last.

Range of an Element using Binary Search

Here if our Boolean flag f is true then we are going to find the first occurrence of our target element. so, we consider the left part of the array. Otherwise, we consider the right part of the array to find the last occurrence of our target element.

Applications

Binary Search has extensive applications in algorithmic problem solving as it has logarithmic runtime. It is absolutely a programmer’s delight!.

Let's say finding the square root of an Integer. In Normal Programming, we loop through all the elements from 1 to N to find the square root. Some clever programmers cut the loop in the halfway N/2. but in Binary Search,

square root using Binary Search

Real-world Applications:

debugging a somewhat linear piece of code. if the code has many steps mostly executed in a sequence and there’s a bug, you can isolate the bug by finding the earliest step where the code produces results which are different from the expected ones.

• cherry-picking a bad code change from a release candidate. When pushing a large code release in production one would sometimes find that there’s a problem with that binary. If reverting the whole release wasn’t an option the release engineer would binary search through the code change ids. He would figure out the earliest code change which creates the bug.
• figuring out resource requirements for a large system. one could try running load tests on the system and binary search for the minimum amount of CPUs required to handle a predicted load. (this approach is better than random guessing but much worse than doing some analysis of your system and doing some good educated guesses)
• figuring out how big should your cache size be for a serving system or deciding on the TTL for the cache.

Some of the problems that can only be solved using Binary Search are,

1. Find the instance of a number in the array where duplicates are allowed.

2. Find the number of instances of a number in the array when duplicates are allowed.

3. Find a minimum element in the rotated sorted array or Find the number of times array is rotated.

4. Find a point where arrays start decreasing, the array is first increasing and then decreasing.

References and useful links:

Binary search algorithm

Complexity Analysis of Binary Search - GeeksforGeeks

What are some problems which can be solved using only and only binary search?