二分搜尋 — 實戰題解

# python
# LC 4 - Median of Two Sorted Arrays
# IDEA: binary search the cut i in the shorter array; j = half - i; stop when left maxima <= right minima
# time = O(log(min(m, n))), space = O(1)
def findMedianSortedArrays(nums1, nums2):
    if len(nums1) > len(nums2):
        nums1, nums2 = nums2, nums1          # search the shorter array
    m, n = len(nums1), len(nums2)
    half = (m + n + 1) // 2                  # size of the left half (the larger one when odd)
    left, right = 0, m                       # i = how many of nums1 go to the left half
    while left <= right:
        i = left + (right - left) // 2
        j = half - i
        left1 = nums1[i - 1] if i > 0 else float('-inf')
        right1 = nums1[i] if i < m else float('inf')
        left2 = nums2[j - 1] if j > 0 else float('-inf')
        right2 = nums2[j] if j < n else float('inf')
        if left1 <= right2 and left2 <= right1:          # a valid cut
            if (m + n) % 2 == 1:
                return max(left1, left2)
            return (max(left1, left2) + min(right1, right2)) / 2
        if left1 > right2:
            right = i - 1                    # took too many from nums1
        else:
            left = i + 1                     # took too few from nums1
    return 0.0                               # unreachable for sorted input

// java
// LC 4 - Median of Two Sorted Arrays
// IDEA: binary search the cut in the shorter array; the other cut follows from the half size
// 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 half = (m + n + 1) / 2;
    int left = 0, right = m;
    while (left <= right) {
        int i = left + (right - left) / 2;
        int j = half - i;
        int left1  = i == 0 ? Integer.MIN_VALUE : nums1[i - 1];
        int right1 = i == m ? Integer.MAX_VALUE : nums1[i];
        int left2  = j == 0 ? Integer.MIN_VALUE : nums2[j - 1];
        int right2 = j == n ? Integer.MAX_VALUE : nums2[j];
        if (left1 <= right2 && left2 <= right1) {
            if ((m + n) % 2 == 1) return Math.max(left1, left2);
            return (Math.max(left1, left2) + (double) Math.min(right1, right2)) / 2.0;
        } else if (left1 > right2) {
            right = i - 1;
        } else {
            left = i + 1;
        }
    }
    return 0.0;
}

# python
# LC 278 - First Bad Version
# IDEA: lower bound on the boolean API: the first version where isBadVersion turns True
# time = O(log n), space = O(1)
def firstBadVersion(n, isBadVersion):
    left, right = 1, n
    while left < right:
        mid = left + (right - left) // 2
        if isBadVersion(mid):
            right = mid              # mid is bad: the first bad one is mid or earlier
        else:
            left = mid + 1           # mid is good: the first bad one is after it
    return left

// java
// LC 278 - First Bad Version
// IDEA: lower bound on the boolean API
// time = O(log n), space = O(1)
public int firstBadVersion(int n) {
    int left = 1, right = n;
    while (left < right) {
        int mid = left + (right - left) / 2;   // (left + right) overflows when n is near 2^31
        if (isBadVersion(mid)) right = mid;
        else left = mid + 1;
    }
    return left;
}

# python
# LC 744 - Find Smallest Letter Greater Than Target
# IDEA: upper bound (first letter > target) on a half-open range, then wrap with % n
# time = O(log n), space = O(1)
def nextGreatestLetter(letters, target):
    left, right = 0, len(letters)            # half-open [left, right): right == n means "none"
    while left < right:
        mid = left + (right - left) // 2
        if letters[mid] <= target:
            left = mid + 1                   # not strictly greater: the answer is to the right
        else:
            right = mid
    return letters[left % len(letters)]      # left == n wraps around to letters[0]

# python
# LC 1150 - Check If a Number Is Majority Element in a Sorted Array
# IDEA: lower bound = start of target's run; majority iff nums[start + n // 2] == target
# time = O(log n), space = O(1)
def isMajorityElement(nums, target):
    n = len(nums)
    left, right = 0, n
    while left < right:                      # first index with nums[i] >= target
        mid = left + (right - left) // 2
        if nums[mid] < target:
            left = mid + 1
        else:
            right = mid
    end = left + n // 2                      # a run longer than n / 2 must still cover this index
    return end < n and nums[end] == target

// java
// LC 1150 - Check If a Number Is Majority Element in a Sorted Array
// IDEA: lower bound = start of target's run; majority iff nums[start + n / 2] == target
// time = O(log n), space = O(1)
public boolean isMajorityElement(int[] nums, int target) {
    int n = nums.length;
    int left = 0, right = n;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) left = mid + 1;
        else right = mid;
    }
    int end = left + n / 2;
    return end < n && nums[end] == target;
}

nums = [2,4,5,5,5,5,5,6,6], target = 5, n = 9
lower bound of 5 -> index 2
index 2 + 9 // 2 = 6, nums[6] = 5 == target -> true

index:  0  1  2  3  4  5  6  7  8
value:  2  4 [5] 5  5  5 [5] 6  6
             start        ^ still 5 iff the run is longer than n / 2

# python
# LC 540 - Single Element in a Sorted Array
# IDEA: probe even mids; an intact pair (nums[mid] == nums[mid+1]) means the single is to the right
# time = O(log n), space = O(1)
def singleNonDuplicate(nums):
    left, right = 0, len(nums) - 1
    while left < right:
        mid = left + (right - left) // 2
        if mid % 2 == 1:
            mid -= 1                         # align mid to the start of a pair
        if nums[mid] == nums[mid + 1]:
            left = mid + 2                   # pair intact: the single is after this pair
        else:
            right = mid                      # pair broken: the single is at mid or before
    return nums[left]

// java
// LC 540 - Single Element in a Sorted Array
// IDEA: probe even mids; an intact pair means the single is to the right
// time = O(log n), space = O(1)
public int singleNonDuplicate(int[] nums) {
    int left = 0, right = nums.length - 1;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (mid % 2 == 1) mid--;
        if (nums[mid] == nums[mid + 1]) left = mid + 2;
        else right = mid;
    }
    return nums[left];
}

# python
# LC 658 - Find K Closest Elements
# IDEA: binary search the window start i in [0, n - k]; move right while arr[i] is farther than arr[i + k]
# time = O(log(n - k) + k), space = O(1) besides the output
def findClosestElements(arr, k, x):
    left, right = 0, len(arr) - k
    while left < right:
        mid = left + (right - left) // 2
        if x - arr[mid] > arr[mid + k] - x:
            left = mid + 1                   # arr[mid] is farther than arr[mid + k]: start later
        else:
            right = mid                      # arr[mid] is at least as close (ties keep the smaller)
    return arr[left:left + k]

# python
# LC 436 - Find Right Interval
# IDEA: sort (start, original index) once; per interval, lower-bound end_i among the starts
# time = O(n log n), space = O(n)
import bisect

def findRightInterval(intervals):
    pairs = sorted((start, i) for i, (start, _) in enumerate(intervals))
    starts = [start for start, _ in pairs]           # bisect needs a plain sorted list
    result = []
    for _, end in intervals:
        j = bisect.bisect_left(starts, end)          # findLeft: first start >= end
        result.append(pairs[j][1] if j < len(pairs) else -1)
    return result

intervals = [[3,4],[2,3],[1,2]]          original indices 0, 1, 2
pairs     = [(1,2), (2,1), (3,0)]        sorted by start
[3,4]: end 4 -> no start >= 4            -> -1
[2,3]: end 3 -> first start >= 3 = (3,0) -> 0
[1,2]: end 2 -> first start >= 2 = (2,1) -> 1

# python
# LC 154 - Find Minimum in Rotated Sorted Array II
# IDEA: compare mid with right; on equality the right end is a duplicate, so drop it
# time = O(log n) average, O(n) worst case (all equal); space = O(1)
def findMin(nums):
    left, right = 0, len(nums) - 1
    while left < right:
        mid = left + (right - left) // 2
        if nums[mid] < nums[right]:
            right = mid                      # mid is in the right run: min is at mid or left of it
        elif nums[mid] > nums[right]:
            left = mid + 1                   # mid is in the left run: min is after mid
        else:
            right -= 1                       # equal: nums[right] has a copy at mid, drop it
    return nums[left]

// java
// LC 154 - Find Minimum in Rotated Sorted Array II
// IDEA: compare mid with right; on equality drop the right end
// time = O(log n) average, O(n) worst case; space = O(1)
public int findMin(int[] nums) {
    int left = 0, right = nums.length - 1;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < nums[right]) right = mid;
        else if (nums[mid] > nums[right]) left = mid + 1;
        else right--;
    }
    return nums[left];
}

# python
# LC 852 - Peak Index in a Mountain Array
# IDEA: half-open squeeze toward the higher neighbour; the window always holds the peak
# time = O(log n), space = O(1)
def peakIndexInMountainArray(arr):
    left, right = 0, len(arr) - 1
    while left < right:
        mid = left + (right - left) // 2
        if arr[mid] < arr[mid + 1]:
            left = mid + 1                   # rising: the peak is to the right
        else:
            right = mid                      # falling: the peak is mid or to the left
    return left

# python
# LC 1095 - Find in Mountain Array
# IDEA: peak via the slope search, then an ascending search on [0, peak] and a descending one on [peak + 1, n - 1]
# time = O(log n), space = O(1)
class Solution:
    def findInMountainArray(self, target, mountain_arr):
        n = mountain_arr.length()

        left, right = 0, n - 1                       # 1) the peak
        while left < right:
            mid = left + (right - left) // 2
            if mountain_arr.get(mid) < mountain_arr.get(mid + 1):
                left = mid + 1
            else:
                right = mid
        peak = left

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

    def search(self, arr, target, left, right, ascending):
        while left <= right:
            mid = left + (right - left) // 2
            value = arr.get(mid)
            if value == target:
                return mid
            if (value < target) == ascending:        # ascending: too small -> right; descending: too big -> right
                left = mid + 1
            else:
                right = mid - 1
        return -1

// java
// LC 1095 - Find in Mountain Array
// IDEA: peak via the slope search, then an ascending and a descending Template 1 search
// time = O(log n), space = O(1)
class Solution {
    public int findInMountainArray(int target, MountainArray arr) {
        int n = arr.length();
        int left = 0, right = n - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (arr.get(mid) < arr.get(mid + 1)) left = mid + 1;
            else right = mid;
        }
        int peak = left;

        int index = search(arr, target, 0, peak, true);
        if (index != -1) return index;
        return search(arr, target, peak + 1, n - 1, false);
    }

    private int search(MountainArray arr, int target, int left, int right, boolean ascending) {
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int value = arr.get(mid);
            if (value == target) return mid;
            if ((value < target) == ascending) left = mid + 1;
            else right = mid - 1;
        }
        return -1;
    }
}

arr = [1,2,3,4,5,3,1], target = 3
peak search  -> peak = 4 (value 5)
ascending  [0, 4]: mid 2 -> 3 == target -> return 2     (index 5 also holds 3, but 2 is smaller)

# python
# LC 367 - Valid Perfect Square
# IDEA: first r in [1, num] with r * r >= num; a perfect square iff r * r == num
# time = O(log num), space = O(1)
def isPerfectSquare(num):
    left, right = 1, num
    while left < right:
        mid = left + (right - left) // 2
        if mid * mid >= num:
            right = mid                      # mid is big enough: the root is mid or smaller
        else:
            left = mid + 1
    return left * left == num

// java
// LC 367 - Valid Perfect Square
// IDEA: first r with r * r >= num, in long to avoid overflow
// time = O(log num), space = O(1)
public boolean isPerfectSquare(int num) {
    long left = 1, right = num;
    while (left < right) {
        long mid = left + (right - left) / 2;
        if (mid * mid >= num) right = mid;
        else left = mid + 1;
    }
    return left * left == num;
}

# python
# LC 1060 - Missing Element in Sorted Array
# IDEA: missing(i) = nums[i] - nums[0] - i is monotone; find the first index with missing(i) >= k
# time = O(log n), space = O(1)
def missingElement(nums, k):
    def missing(i):
        return nums[i] - nums[0] - i         # numbers absent between nums[0] and nums[i]

    left, right = 0, len(nums)               # right = n: the answer may lie past the last element
    while left < right:
        mid = left + (right - left) // 2
        if missing(mid) >= k:
            right = mid
        else:
            left = mid + 1
    # left = first index with >= k missing, so index left - 1 has < k; the answer is past nums[left - 1]
    return nums[left - 1] + k - missing(left - 1)

nums = [4,7,9,10], k = 3
missing:  [0, 2, 3, 3]
first index with missing >= 3 -> 2
answer = nums[1] + 3 - missing(1) = 7 + 3 - 2 = 8      (missing numbers: 5, 6, 8)

# python
# LC 441 - Arranging Coins
# IDEA: last k in [0, n] with k * (k + 1) // 2 <= n; upper mid so left = mid always moves
# time = O(log n), space = O(1)
def arrangeCoins(n):
    left, right = 0, n
    while left < right:
        mid = left + (right - left + 1) // 2  # upper mid
        if mid * (mid + 1) // 2 <= n:
            left = mid                        # mid rows fit: the answer is mid or more
        else:
            right = mid - 1
    return left

// java
// LC 441 - Arranging Coins
// IDEA: last k with k * (k + 1) / 2 <= n, in long; upper mid
// time = O(log n), space = O(1)
public int arrangeCoins(int n) {
    long left = 0, right = n;
    while (left < right) {
        long mid = left + (right - left + 1) / 2;
        if (mid * (mid + 1) / 2 <= n) left = mid;
        else right = mid - 1;
    }
    return (int) left;
}