二分搜尋 — 範例題解

# 167 Two Sum II - Input array is sorted
class Solution(object):
    def twoSum(self, numbers, target):
        for i in range(len(numbers)):
            l, r = i+1, len(numbers)-1
            tmp = target - numbers[i]
            while l <= r:
                mid = l + (r-l)//2
                if numbers[mid] == tmp:
                    return [i+1, mid+1]
                elif numbers[mid] < tmp:
                    l = mid+1
                else:
                    r = mid-1

If nums[mid] < nums[mid + 1]  →  peak is on the RIGHT  (move l = mid + 1)
If nums[mid] > nums[mid + 1]  →  peak is on the LEFT   (move r = mid)

         peak
        /    \
       /      \
-∞ ___/        \___ -∞

         ?
        /
       /
 .... mid  mid+1 ....
      low  HIGH

You are on an upward slope. Two sub-cases:
  a) The slope eventually drops → peak is somewhere to the right
  b) The slope never drops → last element is a peak (because -∞ is on its right)

Either way, a peak MUST exist to the right → l = mid + 1

Example: nums = [1, 2, 3, 1]
                    ^mid ^mid+1
nums[mid]=2 < nums[mid+1]=3  → uphill → move RIGHT
                        ^--- peak is here (index 2, value 3)

 ....  mid  mid+1 ....
       HIGH  low
          \
           \
            ?

You are on a downward slope. Two sub-cases:
  a) nums[mid] > nums[mid-1]: mid itself IS a peak
  b) nums[mid] < nums[mid-1]: the slope was already rising from the left,
     so a peak exists somewhere to the left of mid

Either way, the peak is at mid or to the left → r = mid

Example: nums = [1, 2, 1, 3, 5, 6, 4]
                               ^mid ^mid+1
nums[mid]=5 > nums[mid+1]=6?  No — pick a better example:
                                  ^mid  ^mid+1
nums[mid]=6 > nums[mid+1]=4  → downhill → move LEFT (r = mid, keep mid)
              ^--- peak is here (index 5, value 6)

nums = [1, 2, 3, 1]
        0  1  2  3

l=0, r=3:  mid=1, nums[1]=2 < nums[2]=3  → uphill → l=2
           [_, _, 2, 3]
                  l  r

l=2, r=3:  mid=2, nums[2]=3 > nums[3]=1  → downhill → r=2
           [_, _, 3, _]
                  l
                  r

l==r → return 2  ✓  (nums[2]=3 is the peak)

nums = [1, 2, 1, 3, 5, 6, 4]
        0  1  2  3  4  5  6

l=0, r=6:  mid=3, nums[3]=3 < nums[4]=5  → uphill → l=4
l=4, r=6:  mid=5, nums[5]=6 > nums[6]=4  → downhill → r=5
l=4, r=5:  mid=4, nums[4]=5 < nums[5]=6  → uphill → l=5
l=5, r=5:  l==r → return 5  ✓  (nums[5]=6 is the peak)

// ✅ Correct: while (l < r)
while (l < r) {
    int mid = (l + r) / 2;
    if (nums[mid] > nums[mid + 1])
        r = mid;       // Keep mid, since it may be the peak
    else
        l = mid + 1;   // mid is not the peak, skip it
}
// When l == r, that IS the peak index
return l;

# LC 162 Find Peak Element, LC 852 Peak Index in a Mountain Array
# V0'
# IDEA : RECURSIVE BINARY SEARCH
class Solution(object):
    def findPeakElement(self, nums):

        def help(nums, l, r):
            if l == r:
                return l
            mid = l + (r - l) // 2
            if (nums[mid] > nums[mid+1]):
                return help(nums, l, mid) # r = mid
            return help(nums, mid+1, r) # l = mid + 1
            
        return help(nums, 0, len(nums)-1)

// java
// LC 162
// V2
// IDEA: RECURSIVE BINARY SEARCH
// https://leetcode.com/problems/find-peak-element/editorial/
    // NOTE : ONLY have to compare index i with index i + 1 (its right element)
    //        ; otherwise, i-1 already returned as answer
    public int findPeakElement_2(int[] nums) {
        return search(nums, 0, nums.length - 1);
    }
    public int search(int[] nums, int l, int r) {
        if (l == r)
            return l;
        int mid = (l + r) / 2;
        if (nums[mid] > nums[mid + 1])
            return search(nums, l, mid);
        return search(nums, mid + 1, r);
    }

# 367 Valid Perfect Square, LC 69 Sqrt(x)
# V0'
# IDEA : BINARY SEARCH
class Solution(object):
    def isPerfectSquare(self, num):
        left, right = 0, num
        while left <= right:
            ### NOTE : there is NO mid * mid == num condition
            mid = (left + right) / 2
            if mid * mid >= num:
                right = mid - 1
            else:
                left = mid + 1
        ### NOTE this
        return left * left == num

// java
// LC 367
public boolean isPerfectSquare(int num) {

    if (num < 2) {
        return true;
    }

    long left = 2;
    long right = num / 2; // NOTE !!!, "long right = num;" is OK as well
    long x;
    long guessSquared;

    while (left <= right) {
        x = (left + right) / 2;
        guessSquared = x * x;
        if (guessSquared == num) {
            return true;
        }
        if (guessSquared > num) {
            right = x - 1;
        } else {
            left = x + 1;
        }
    }
    return false;
}

# LC 069 Sqrt(x)
# V0
# IDEA : binary search
class Solution(object):
    def mySqrt(self, num):
        if num <= 1:
            return num
        l = 0
        r = num - 1
        while r >= l:
            mid = l + (r - l) // 2
            if mid * mid == num:
                return mid
            elif mid * mid > num:
                r = mid - 1
            else:
                l = mid + 1
        return l if l * l < num else l - 1

# LC 209 Minimum Size Subarray Sum
### NOTE : there is also sliding window approach
# V1' 
# http://bookshadow.com/weblog/2015/05/12/leetcode-minimum-size-subarray-sum/
# IDEA : BINARY SEARCH 
class Solution:
    def minSubArrayLen(self, s, nums):
        size = len(nums)
        left, right = 0, size
        bestAns = 0
        while left <= right:
            mid = (left + right) / 2
            if self.solve(mid, s, nums):
                bestAns = mid
                right = mid - 1
            else:
                left = mid + 1
        return bestAns

    def solve(self, l, s, nums):
        sums = 0
        for x in range(len(nums)):
            sums += nums[x]
            if x >= l:
                sums -= nums[x - l]
            if sums >= s:
                return True
        return False

// LC 278 - First Bad Version
// IDEA: Binary search for left boundary — first bad version
// time = O(log N), space = O(1)
public int firstBadVersion(int n) {
    int l = 1, r = n;
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (isBadVersion(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}

# LC 658. Find K Closest Elements
# V1'
# https://blog.csdn.net/fuxuemingzhu/article/details/82968136
# IDEA : TWO POINTERS 
class Solution(object):
    def findClosestElements(self, arr, k, x):
        # since the array already sorted, arr[-1] must be the biggest one,
        # while arr[0] is the smallest one
        # so if the distance within arr[-1],  x >  arr[0],  x
        # then remove the arr[-1] since we want to keep k elements with smaller distance,
        # and vice versa (remove arr[0]) 
        while len(arr) > k:
            if x - arr[0] <= arr[-1] - x:
                arr.pop()
            else:
                arr.pop(0)
        return arr

# LC 744 Find Smallest Letter Greater Than Target
class Solution(object):
    def nextGreatestLetter(self, letters, target):
        l, r = 0, len(letters)
        
        # Use half-open boundary [l, r)
        while l < r:
            mid = l + (r - l) // 2
            if letters[mid] <= target:  # Need strictly greater
                l = mid + 1
            else:
                r = mid
        
        # Handle circular array - if no letter greater than target, return first
        return letters[l % len(letters)]

// LC 441 Arranging Coins
public int arrangeCoins(int n) {
    long l = 0, r = n;
    
    while (l <= r) {
        long mid = l + (r - l) / 2;
        long coins = mid * (mid + 1) / 2;  // Sum of 1+2+...+mid
        
        if (coins == n) {
            return (int) mid;
        } else if (coins < n) {
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    
    return (int) r;  // Return the complete rows we can form
}

// LC 154 Find Minimum in Rotated Sorted Array II (with duplicates)
public int findMin(int[] nums) {
    int l = 0, r = nums.length - 1;
    
    while (l < r) {
        int mid = l + (r - l) / 2;
        
        if (nums[mid] < nums[r]) {
            // Right half is sorted, minimum is in left half (including mid)
            r = mid;
        } else if (nums[mid] > nums[r]) {
            // Left half is sorted, minimum is in right half
            l = mid + 1;
        } else {
            // nums[mid] == nums[r], can't determine which half to search
            // Reduce search space by 1
            r--;
        }
    }
    
    return nums[l];
}

# LC 1060 Missing Element in Sorted Array
class Solution(object):
    def missingElement(self, nums, k):
        def missing_count(idx):
            # How many numbers are missing up to nums[idx]
            return nums[idx] - nums[0] - idx
        
        n = len(nums)
        
        # If k-th missing number is beyond the array
        if k > missing_count(n - 1):
            return nums[-1] + k - missing_count(n - 1)
        
        l, r = 0, n - 1
        
        # Find the largest index where missing_count < k
        while l < r - 1:
            mid = l + (r - l) // 2
            if missing_count(mid) < k:
                l = mid
            else:
                r = mid
        
        # The k-th missing number is between nums[l] and nums[r]
        return nums[l] + k - missing_count(l)

// LC 4 - Median of Two Sorted Arrays
// IDEA: Binary search partition on smaller array
// time = O(log(min(M,N))), space = O(1)
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    if (nums1.length > nums2.length) return findMedianSortedArrays(nums2, nums1);
    int m = nums1.length, n = nums2.length;
    int l = 0, r = m;
    while (l <= r) {
        int partX = (l + r) / 2;
        int partY = (m + n + 1) / 2 - partX;
        int maxLeftX  = partX == 0 ? Integer.MIN_VALUE : nums1[partX-1];
        int minRightX = partX == m ? Integer.MAX_VALUE : nums1[partX];
        int maxLeftY  = partY == 0 ? Integer.MIN_VALUE : nums2[partY-1];
        int minRightY = partY == n ? Integer.MAX_VALUE : nums2[partY];
        if (maxLeftX <= minRightY && maxLeftY <= minRightX) {
            if ((m + n) % 2 == 0)
                return (Math.max(maxLeftX, maxLeftY) + Math.min(minRightX, minRightY)) / 2.0;
            else
                return Math.max(maxLeftX, maxLeftY);
        } else if (maxLeftX > minRightY) r = partX - 1;
        else l = partX + 1;
    }
    return 0;
}

// LC 981 - Time Based Key-Value Store
// IDEA: HashMap of key -> sorted list of (timestamp, value); binary search on query
// time = O(log N) per get, O(1) per set, space = O(N)
class TimeMap {
    Map<String, List<int[]>> map = new HashMap<>(); // val stored as [timestamp, valueIndex]
    Map<String, List<String>> vals = new HashMap<>();
    public void set(String key, String value, int timestamp) {
        map.computeIfAbsent(key, k -> new ArrayList<>()).add(new int[]{timestamp});
        vals.computeIfAbsent(key, k -> new ArrayList<>()).add(value);
    }
    public String get(String key, int timestamp) {
        if (!map.containsKey(key)) return "";
        List<int[]> times = map.get(key);
        int l = 0, r = times.size() - 1, idx = -1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (times.get(mid)[0] <= timestamp) { idx = mid; l = mid + 1; }
            else r = mid - 1;
        }
        return idx == -1 ? "" : vals.get(key).get(idx);
    }
}

// LC 540 - Single Element in a Sorted Array
// IDEA: Binary search — check if pair pattern holds at mid (even index)
// time = O(log N), space = O(1)
public int singleNonDuplicate(int[] nums) {
    int l = 0, r = nums.length - 1;
    while (l < r) {
        int mid = (l + r) / 2;
        if (mid % 2 == 1) mid--; // ensure mid is even
        if (nums[mid] == nums[mid + 1]) l = mid + 2; // pair intact, single is to the right
        else r = mid;                                  // pair broken, single is here or left
    }
    return nums[l];
}

// Find first occurrence of target in sorted array
private int findFirstIndex(int[] nums, int target) {
    int low = 0, high = nums.length - 1;
    int firstIdx = -1;

    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (nums[mid] == target) {
            firstIdx = mid;       // record potential answer
            high = mid - 1;       // keep searching LEFT for earlier occurrence
        } else if (nums[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return firstIdx;
}

// LC 1150 - Check If a Number Is Majority Element in a Sorted Array
// time: O(log N), space: O(1)
public boolean isMajorityElement(int[] nums, int target) {
    int n = nums.length;

    // Step 1: Find first occurrence of target
    int firstIndex = findFirstIndex(nums, target);

    // Step 2: If not found, can't be majority
    if (firstIndex == -1) return false;

    // Step 3: Check if element at (firstIndex + n/2) is still target
    // If yes → target appears at least (n/2 + 1) times → majority
    int majorityIndex = firstIndex + n / 2;
    return majorityIndex < n && nums[majorityIndex] == target;
}

private int findFirstIndex(int[] nums, int target) {
    int low = 0, high = nums.length - 1, firstIdx = -1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (nums[mid] == target) {
            firstIdx = mid;
            high = mid - 1;    // search left for earlier occurrence
        } else if (nums[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return firstIdx;
}

// Uses two binary searches: first index of target, first index of (target+1)
public boolean isMajorityElement_v1(int[] nums, int target) {
    int left  = lowerBound(nums, target);      // first index >= target
    int right = lowerBound(nums, target + 1);  // first index >= target+1
    return right - left > nums.length / 2;
}

private int lowerBound(int[] nums, int x) {
    int left = 0, right = nums.length;
    while (left < right) {
        int mid = (left + right) >>> 1;
        if (nums[mid] >= x) right = mid;
        else left = mid + 1;
    }
    return left;
}

nums = [2,4,5,5,5,5,5,6,6], target = 5, N = 9

findFirstIndex(5) → index 2

majorityIndex = 2 + 9/2 = 2 + 4 = 6
nums[6] = 5 == target ✓  → return true

Intuition:
index:  0  1  2  3  4  5  6  7  8
value:  2  4 [5] 5  5  5 [5] 6  6
           first↑           ↑ must still be 5 if majority

intervals = [[3,4],[2,3],[1,2]]   (original indices 0,1,2)

sort starts with their index →  starts = [(1,2), (2,1), (3,0)]
                                            ^val,idx

For interval [2,3]:  end = 3  → first start >= 3  → (3,0) → original index 0  ✅
For interval [1,2]:  end = 2  → first start >= 2  → (2,1) → original index 1  ✅
For interval [3,4]:  end = 4  → no start >= 4                → -1

# LC 436 Find Right Interval
# V1: manual lower-bound binary search
# time = O(n log n), space = O(n)
class Solution(object):
    def findRightInterval(self, intervals):
        n = len(intervals)

        # NOTE !!! collect BOTH `start val` AND `original idx`, then sort
        # -> sorting keeps start glued to its original index
        starts = [(intervals[i][0], i) for i in range(n)]
        starts.sort()                          # sort by start (unique)

        res = [-1] * n
        for i in range(n):
            target = intervals[i][1]           # we need first start >= end_i

            # ---- lower bound: first start >= target ----
            left, right, ans = 0, n - 1, -1
            while left <= right:
                mid = (left + right) // 2
                if starts[mid][0] >= target:
                    ans = starts[mid][1]       # record original index (candidate)
                    right = mid - 1            # keep searching LEFT for a smaller start
                else:
                    left = mid + 1
            res[i] = ans
        return res

import bisect
# time = O(n log n), space = O(n)
class Solution(object):
    def findRightInterval(self, intervals):
        n = len(intervals)
        # (start, original_idx) sorted by start
        starts = sorted([[iv[0], i] for i, iv in enumerate(intervals)])
        just_starts = [s[0] for s in starts]   # bisect needs a plain sorted list

        res = [-1] * n
        for i, iv in enumerate(intervals):
            idx = bisect.bisect_left(just_starts, iv[1])   # first start >= end_i
            if idx < n:
                res[i] = starts[idx][1]        # map sorted pos -> original index
        return res

1) find the PEAK             -> hill-climbing binary search (same as LC 162 / LC 852, §2 above)
2) binary search [0, peak]   -> ASCENDING  order
3) binary search [peak+1, n) -> DESCENDING order   <-- the twist most people miss

// java
// LC 1095 - Find in Mountain Array
// IDEA: 1) hill-climb binary search for the peak, 2) ascending BS on left half,
//       3) descending BS on right half (flip the comparison)
// time = O(log n)  (~3 * log n get() calls), space = O(1)
class Solution {
    public int findInMountainArray(int target, MountainArray arr) {
        int n = arr.length();
        int l = 0, r = n - 1;
        while (l < r) {                                     // 1) peak = first i with a[i] > a[i+1]
            int mid = l + (r - l) / 2;
            if (arr.get(mid) < arr.get(mid + 1)) l = mid + 1;   // uphill  -> peak on the right
            else r = mid;                                       // downhill-> peak at mid or left
        }
        int peak = l;

        int idx = bs(arr, target, 0, peak, true);           // 2) ascending half (smallest index first)
        if (idx != -1) return idx;
        return bs(arr, target, peak + 1, n - 1, false);     // 3) descending half
    }

    // one binary search that handles BOTH orders
    private int bs(MountainArray arr, int target, int l, int r, boolean asc) {
        while (l <= r) {
            int mid = l + (r - l) / 2;
            int val = arr.get(mid);
            if (val == target) return mid;
            if ((val < target) == asc) l = mid + 1;   // asc: too small -> right; desc: too small -> left
            else r = mid - 1;
        }
        return -1;
    }
}

# python
# LC 1095 - Find in Mountain Array
# IDEA: peak via hill-climbing BS, then ascending BS on the left half and descending BS on the right
# time = O(log n), space = O(1)
class Solution:
    def findInMountainArray(self, target, mountain_arr):
        n = mountain_arr.length()

        # 1) find peak
        l, r = 0, n - 1
        while l < r:
            mid = (l + r) // 2
            if mountain_arr.get(mid) < mountain_arr.get(mid + 1):
                l = mid + 1          # uphill  -> peak on the right
            else:
                r = mid              # downhill-> peak at mid or to the left
        peak = l

        # 2) ascending half first (we want the SMALLEST index)
        idx = self.bs(mountain_arr, target, 0, peak, True)
        if idx != -1:
            return idx
        # 3) descending half
        return self.bs(mountain_arr, target, peak + 1, n - 1, False)

    def bs(self, arr, target, l, r, asc):
        while l <= r:
            mid = (l + r) // 2
            val = arr.get(mid)
            if val == target:
                return mid
            if (val < target) == asc:   # asc -> move right; desc -> move left
                l = mid + 1
            else:
                r = mid - 1
        return -1

nums = [10, 9, 2, 5, 3, 7, 101, 18]
10  -> [10]
 9  -> [9]              (replace: length-1 run can end smaller)
 2  -> [2]
 5  -> [2,5]
 3  -> [2,3]            (replace 5)
 7  -> [2,3,7]
101 -> [2,3,7,101]
 18 -> [2,3,7,18]       -> answer = 4

// java
// LC 300 - Longest Increasing Subsequence
// IDEA: patience sorting - tails[k] = smallest tail of an increasing run of length k+1,
//       binary search (lower_bound) for the slot to extend or overwrite
// time = O(n log n), space = O(n)
public int lengthOfLIS(int[] nums) {
    int[] tails = new int[nums.length];
    int size = 0;
    for (int x : nums) {
        int l = 0, r = size;
        while (l < r) {                 // lower_bound: first tails[i] >= x
            int mid = l + (r - l) / 2;
            if (tails[mid] < x) l = mid + 1;
            else r = mid;
        }
        tails[l] = x;                   // overwrite ...
        if (l == size) size++;          // ... or append (l == size)
    }
    return size;
}

# python
# LC 300 - Longest Increasing Subsequence
# IDEA: keep sorted `tails` array, bisect_left = lower_bound -> replace, else append
# time = O(n log n), space = O(n)
import bisect

class Solution:
    def lengthOfLIS(self, nums):
        tails = []
        for x in nums:
            i = bisect.bisect_left(tails, x)   # first tail >= x
            if i == len(tails):
                tails.append(x)                # x extends the longest run
            else:
                tails[i] = x                   # smaller tail for the same length
        return len(tails)

strictly increasing (LC 300)      -> bisect_left  / lower_bound  (first tail >= x)
non-decreasing (duplicates OK)    -> bisect_right / upper_bound  (first tail >  x)

# python
# LC 354 - Russian Doll Envelopes
# IDEA: sort by (w asc, h desc) -> reduces to LIS on heights
# time = O(n log n), space = O(n)
import bisect

def maxEnvelopes(envelopes):
    envelopes.sort(key=lambda e: (e[0], -e[1]))   # ties: h DESC blocks same-width chains
    tails = []
    for _, h in envelopes:
        i = bisect.bisect_left(tails, h)
        if i == len(tails):
            tails.append(h)
        else:
            tails[i] = h
    return len(tails)

// java
// LC 354 - Russian Doll Envelopes
// IDEA: sort (w asc, h desc), then LIS on the heights array (reuse lengthOfLIS above)
// time = O(n log n), space = O(n)
public int maxEnvelopes(int[][] envelopes) {
    Arrays.sort(envelopes, (a, b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);
    int[] heights = new int[envelopes.length];
    for (int i = 0; i < envelopes.length; i++) heights[i] = envelopes[i][1];
    return lengthOfLIS(heights);
}

w      = [1,  3,  2]
prefix = [1,  4,  6]
target:   1 | 2 3 4 | 5 6
index :   0 |   1   |  2

// java
// LC 528 - Random Pick with Weight
// IDEA: prefix sums split [1, total] into per-index ranges; lower_bound maps a uniform draw to an index
// time = ctor O(n), pickIndex O(log n); space = O(n)
class Solution {
    private int[] prefix;
    private Random rand = new Random();

    public Solution(int[] w) {
        prefix = new int[w.length];
        int s = 0;
        for (int i = 0; i < w.length; i++) { s += w[i]; prefix[i] = s; }
    }

    public int pickIndex() {
        int target = rand.nextInt(prefix[prefix.length - 1]) + 1;   // uniform in [1, total]
        int l = 0, r = prefix.length - 1;
        while (l < r) {                       // lower_bound: first prefix >= target
            int mid = l + (r - l) / 2;
            if (prefix[mid] < target) l = mid + 1;
            else r = mid;
        }
        return l;
    }
}

# python
# LC 528 - Random Pick with Weight
# IDEA: prefix sums + bisect_left (lower bound) on a uniform draw in [1, total]
# time = __init__ O(n), pickIndex O(log n); space = O(n)
import bisect, random

class Solution:
    def __init__(self, w):
        self.prefix = []
        s = 0
        for x in w:
            s += x
            self.prefix.append(s)
        self.total = s

    def pickIndex(self):
        target = random.randint(1, self.total)          # inclusive on both ends
        return bisect.bisect_left(self.prefix, target)  # first prefix >= target