Binary Search variations that you should know

Binary Search is a useful algorithm to search for a target value in a sorted list of elements.

Standard Binary Search:

• Get the middle element of the sorted list and compare with the target value. If the number equals the target, we found the value.
• If the middle element is less than the target, then we have to search in the right half of the sorted array.
• Else we search in the left half of the sorted array.

Let us look at the code for standard Binary Search.

def binarySearch(self, nums: List[int], target: int) -> int:

    left = 0
    right = len(nums) - 1

    while left <= right:
        mid = (left + right) // 2

        if nums[mid] == target:
            return mid

        # search in the right half       
        if nums[mid] < target:
            left = mid + 1

        # search in the left half      
        else:
            right = mid - 1

    return -1

At each iteration of the while loop, the above algorithm divides our search space by half, so the overall time complexity will be O(log N). This is a significant reduction compared to the O(N) time complexity incurred by Linear Search. Now let’s look at a variation.

Binary Search Variation #1:

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

Assumption: There are no duplicates in the array.

In this case, if a target is not found, we have to find the index of the value immediately greater than the target. Let’s look at an example.

Input: nums = [1,3,5,6], target = 4

Output: 2

In the above example, 4 is not present in the array. If we were to insert it into the array, we should insert it between 3 and 5. So our insert index will be 2.

We can use the standard binary search to find the insert position with a slight variation. Let’s run through the algorithm step by step.

• left = 0, right = 3
• mid = (0 + 3) // 2 = 1
• nums[mid] = nums[1] = 3
• Here 3 < 4, if nums[mid] < target, search the right half of the list
• Then left = mid + 1 => 1 + 1 = 2

• left = 2, right = 3
• mid = (2 + 3) // 2 = 2
• nums[mid] = nums[2] = 5
• Here 5 > 4, if nums[mid] > target, search the left half of the list
• Then right = mid -1 => 2 – 1 = 1

In the above example, we see that the left pointer holds the insert position as we go through the while loop. This is because, by the time we complete the while loop, left pointer will point to the element that is immediately greater than the target value which is where we will insert our target.

Code:

def searchInsert(self, nums: List[int], target: int) -> int:

    left = 0
    right = len(nums) - 1

    while left <= right:
        mid = (left + right) // 2

        if nums[mid] == target:
            return mid

        if nums[mid] < target:
            left = mid + 1

        else:
            right = mid - 1

    return left

Binary Search Variation #2:

Now what if we have to find the index of the element that is just smaller than the given target ie., the greatest element lesser than the target value. Yes, you guessed it! This value is stored by the right pointer, so we return it in that case.

Code:

def searchLesserThanTarget(self, nums: List[int], target: int) -> int:

    left = 0
    right = len(nums) - 1

    while left <= right:
        mid = (left + right) // 2

        if nums[mid] == target:
            return mid

        if nums[mid] < target:
            left = mid + 1

        else:
            right = mid - 1

    return right
        

Hope you enjoyed learning the different variations of Binary Search. Have a great day!