Binary search

Binary search is a technique used to quickly locate a specific item in a sorted list. The algorithm works by comparing the target value to the middle element of the list. If the target value is equal to the middle element, the search is successful. If the target value is less than the middle element, the search continues on the lower half of the list. If the target value is greater than the middle element, the search continues on the upper half of the list. This process continues until the target value is found or the search is unsuccessful.

In python there is built-in library for binary search: bisect

Example with this library:

import bisect

arr = [1,3,4,5,6,7]
print(bisect.bisect_left(arr, 5))

Basic Template

Basic Template of binary search without use of built-in library:

def fn(arr, target):
    left = 0
    right = len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            # do something
            return
        if arr[mid] > target:
            right = mid - 1
        else:
            left = mid + 1

    # left is the insertion point
    return left

Binare search: Version 1

Most basic and elementary form of Binary Search. Search Condition can be determined without comparing to the element’s neighbors (or use specific elements around it). No post-processing required because at each step, you are checking to see if the element has been found. If you reach the end, then you know the element is not found

bisect_1(nums, target)[source]

Given a sorted (in ascending order) integer array nums of n elements and a target value, find the target value in the array.

Time complexity: \(O(\log n)\)

Space complexity: \(O(1)\)

Return type:: int

Binary search: Version 2

An advanced way to implement Binary Search. Use the element’s right neighbor to determine if the condition is met and decide whether to go left or right. Guarantees Search Space is at least 2 in size at each step. Post-processing required. Loop/Recursion ends when you have 1 element left. Need to assess if the remaining element meets the condition.

Binary search: Version 3

An alternative way to implement Binary Search. Use element’s neighbors to determine if condition is met and decide whether to go left or right Gurantees Search Space is at least 3 in size at each step. Post-processing required. Loop/Recursion ends when you have 2 elements left. Need to assess if the remaining elements meet the condition.

Binary Search on Answer

More advanced application is solving of optimisation problems. Optimisation problems are problems which ask to find the maximum or minimum for some value This technique is called “binary search on answer”

Template for optimisation problems:

def optimize(nums, p):
    left, right = min(nums), max(nums)
    def feasible(val):
        # ...
        return val >= p

    while left <= right:
        mid = (left + right) // 2
        if feasible(mid):
            right = mid - 1
        else: left = mid + 1

    return left

minimizeMax(nums: list[int], p: int) → int[source]

Example problem: https://leetcode.com/problems/minimize-the-maximum-difference-of-pairs/ You are given a 0-indexed integer array nums and an integer p. Find p pairs of indices of nums such that the maximum difference amongst all the pairs is minimized. Also, ensure no index appears more than once amongst the p pairs. Note that for a pair of elements at the index i and j, the difference of this pair is |nums[i] - nums[j]|, where |x| represents the absolute value of x. Return the minimum maximum difference among all p pairs. We define the maximum of an empty set to be zero.

Time complexity: \(O(n \log n)\)

Space complexity: \(O(n)\)