Binary Search

Binary search is a search algorithm that finds the first (lower_bound) or last (upper_bound) position of a target value within a sorted array.

It is the most common used search algorithm in computer science, if you find any $O(n\log n)$ algorithm, it is likely to be a binary search algorithm. You should always consider using binary search first especially when there is "test and trial" pattern in the problem and the required solution is a single number.

Codes

Java

public int BinarySearch(int[] nums, int target) {
    int i=0;
    int j=nums.length;
    while (i<j){
        if(nums[(i+j)/2]>target){
            j=(i+j)/2;
        }else if(nums[(i+j)/2]<target){
            i=(i+j)/2+1;
        }else{
            return (i+j)/2;
        }
    }
    return -1;
}

Python

def binary_search(nums, target):
    """
    Binary search algorithm
    :param nums: list of integers
    :param target: target value
    :return: index of the target value
    """
    i=0
    j=len(nums)
    while i<j:
        if nums[(i+j)//2]>target:
            j=(i+j)//2
        elif nums[(i+j)//2]<target:
            i=(i+j)//2+1
        else:
            return (i+j)//2
    return -1

Applications

Leetcode 2528

• Leetcode 2528

It takes a while to realize that binary search is all I need. I tried to use segment tree to solve this problem, but it is too complex to implement and the time complexity is not guaranteed to be $O(n\log n)$ in the insertion of queries.

Intuition

I see I only need to return the minimum power of the city that can be powered by the given cities.

Each test solution can be verified using a single iteration over the cities.

Solution

class Solution:
    def maxPower(self, stations: List[int], r: int, k: int) -> int:
        def canPower(power: int,k: int) -> bool:
            # stored the power range of the latest power station constructed
            # formated as (expiration (inclusive), powersupply)
            power_range=[]
            additional_power=0
            quota=0
            for i,e in enumerate(stations):
                # at most one entry is popped each time
                if power_range and power_range[0][0]<i:
                    additional_power -= power_range.pop(0)[1]
                if e + additional_power < power:
                    required_power = power - e - additional_power
                    k -= required_power
                    power_range.append((i+2*(r+1)-1, required_power))
                    if k < 0:
                        return False
                    additional_power += required_power
            return True
        # first updated the true power of the cities
        n=len(stations)
        cur_power=sum(stations[:r+1])
        true_power=[0]*n
        for i in range(n):
            true_power[i]=cur_power
            if i-r-1>=0:
                cur_power -= stations[i-r-1]
            if i+r<n:
                cur_power += stations[i+r]
        power=true_power
        lo, hi = min(stations), max(stations)+k+1
        while lo < hi:
            mid = (lo + hi) // 2
            if canPower(mid,k):
                hi = mid
            else:
                lo = mid + 1
        return lo