Data Structure & Algorithm Takeaway: Binary Search

TipWhat is binary search?

Binary search is an algorithm searching for a target value within a sorted array.

TipIs there any requirement for the input?

Sorted, array.

TipWhy can binary search improve search efficiency?

Leveraging the access

TipHow does binary search work?

Binary search works by repeatedly dividing the search interval in half. The steps are as follows:

We use Python code to illustrate the process:

def BinarySearch(array: list[int], target: int) -> int:
    n = len(array)

    low = 0
    high = n - 1 
    while low <= high:
        mid = (low + high) // 2
        if target < array[mid]:
            high = mid - 1
        elif target > array[mid]:
            low = mid + 1
        elif target == array[mid]:
            return mid
    
    return -1

TipWhat else can binary search do?

Binary search can be extended for other purposes.

Find the first or last element less than target in a sorted array:

def FirstElementLessThan(array: list[int], target: int) -> int:
    n = len(array)
    low, high = 0, n - 1
    ans = -1
    
    while low <= high:
        mid = (low + high) // 2
        if array[mid] < target:
            ans = mid     
            high = mid - 1  
        else:
            low = mid + 1  
    
    if ans != -1:
        return array[ans]
    return None 

def LastElementLessThan(array: list[int], target: int) -> int:
    n = len(array)
    low, high = 0, n - 1
    ans = -1
    
    while low <= high:
        mid = (low + high) // 2
        if array[mid] < target:
            ans = mid     
            low = mid + 1  
        else:
            high = mid - 1  

    if ans != -1:
        return array[ans]
    return None 

Find all the elements equal to target: Find any target element first by the original binary search first, and then use binary search separately for to find the left and right boundary. (The most intuitive solution might be extending to the left and right end after the binary search. However, its time complexity becomes $O(n)$ when all the elements in the array are equal to the target.)