二分搜尋

// Standard binary search pattern
while (l <= r) {
    int mid = l + (r - l) / 2;

    if (nums[mid] == target) {
        return mid;
    } else if (nums[mid] < target) {
        l = mid + 1;  // All elements [0..mid] are < target
    } else {
        r = mid - 1;  // All elements [mid..end] are > target
    }
}

Visual Representation:

index:     0   ...   r   l   ...   n-1
value:   [< target]  gap  [> target]

Initial:
l=0, r=3
[1, 3, 5, 6]
 l        r

Step 1:
mid = 1, nums[1] = 3
3 < 4, so l = mid + 1 = 2
[1, 3, 5, 6]
       l  r

Step 2:
mid = 2, nums[2] = 5
5 > 4, so r = mid - 1 = 1
[1, 3, 5, 6]
    r  l

Loop ends (l > r):
- r points to 3 (last element < 4)
- l points to 5 (first element > 4)
- Insertion position is l = 2

// LC 35 - The cleanest solution using pointer behavior
public int searchInsert(int[] nums, int target) {
    if (nums == null || nums.length == 0) {
        return 0;
    }

    int l = 0;
    int r = nums.length - 1;

    while (l <= r) {
        int mid = l + (r - l) / 2;

        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }

    // Key insight: l is always the correct insertion position
    return l;
}

// ❌ WRONG: Trying to handle "between mid and mid+1" during the loop
while (l <= r) {
    int mid = l + (r - l) / 2;
    if (nums[mid] == target) return mid;

    // This is unnecessary and error-prone!
    // ❌ WRONG — can cause index out of bounds
    if (mid + 1 <= nums.length - 1 && target < nums[mid+1] && target > nums[mid]) {
        return mid + 1;
    }
    // ...
}

[Left Higher Plateau] > [Right Lower Plateau]
e.g. [3, 4, 5, 1, 2]
      ^^^^^^^^  ^^^^
      left part  right part (contains minimum)

Rotation examples (length 5):
[1, 2, 3, 4, 5]  → already sorted, min at index 0
[5, 1, 2, 3, 4]  → mid < r → right is sorted → go left (r = mid)
[4, 5, 1, 2, 3]  → mid < r → right is sorted → go left (r = mid)
[3, 4, 5, 1, 2]  → mid >= l → left is sorted → go right (l = mid + 1)
[2, 3, 4, 5, 1]  → mid >= l → left is sorted → go right (l = mid + 1)

// LC 153 - Find Minimum in Rotated Sorted Array
// time = O(log N), space = O(1)
public int findMin(int[] nums) {
    int l = 0, r = nums.length - 1;
    int ans = nums[0];

    while (l <= r) {
        // Early exit: current window already sorted → minimum is at l
        if (nums[l] <= nums[r]) {
            ans = Math.min(ans, nums[l]);
            break;
        }

        int mid = l + (r - l) / 2;
        ans = Math.min(ans, nums[mid]);

        if (nums[mid] >= nums[l]) {
            l = mid + 1;  // left plateau → go right
        } else {
            r = mid - 1;  // right plateau → go left
        }
    }
    return ans;
}

// Cleaner: converges l == r to the minimum index
// time = O(log N), space = O(1)
public int findMin(int[] nums) {
    int l = 0, r = nums.length - 1;
    while (r > l) {
        int mid = l + (r - l) / 2;
        if (nums[mid] < nums[r]) {
            r = mid;       // right side sorted → min could be at mid
        } else {
            l = mid + 1;   // left side sorted → min is to the right
        }
    }
    return nums[l];  // l == r → minimum
}

l=0, r=4: nums[l]=3 > nums[r]=2 → rotated
  mid=2, nums[2]=5 >= nums[0]=3 → left plateau → l=3

l=3, r=4: nums[l]=1 < nums[r]=2 → sorted → ans=min(ans,1), break

Answer = 1 ✓

# LC 033. Search in Rotated Sorted Array
# LC 081. Search in Rotated Sorted Array II
# V0
# IDEA : BINARY SEARCH
#        -> CHECK WHICH PART IS ORDERING
#        -> CHECK IF TARGET IS IN WHICH PART
# CASES :
#  1) if mid is on the right of pivot -> array[mid:] is ordering
#     -> check if mid in on the left or right on mid
#     -> binary search on left or right sub array
#  2) if mid in on the left of pivot  -> array[:mid] is ordering
#     -> check if mid in on the left or right on mid
#     -> binary search on left or right sub array
### NOTE : THE NESTED IF ELSE CONDITION 
class Solution(object):
    def search(self, nums, target):
        if not nums: return -1
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == target:
                return mid
            #---------------------------------------------
            # Case 1 :  nums[mid:right] is ordering
            #---------------------------------------------
            # all we need to do is : 1) check if target is within mid - right, and move the left or right pointer
            if nums[mid] < nums[right]:
                # mind NOT use (" nums[mid] < target <= nums[right]")
                # mind the "<="
                if target > nums[mid] and target <= nums[right]: # check the relationship with target, which is different from the default binary search
                    left = mid + 1
                else:
                    right = mid - 1
            #---------------------------------------------
            # Case 2 :  nums[left:mid] is ordering
            #---------------------------------------------
            # all we need to do is : 1) check if target is within left - mid, and move the left or right pointer
            else:
                # # mind NOT use (" nums[left] <= target < nums[mid]")
                # mind the "<="
                if target < nums[mid] and target >= nums[left]:  # check the relationship with target, which is different from the default binary search
                    right = mid - 1
                else:
                    left = mid + 1
        return -1     

// LC 33 - Search in Rotated Sorted Array
// IDEA: Binary search — identify sorted half, narrow range
// time = O(log N), space = O(1)
public int search(int[] nums, int target) {
    int l = 0, r = nums.length - 1;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (nums[mid] == target) return mid;
        if (nums[l] <= nums[mid]) {           // left half is sorted
            if (nums[l] <= target && target < nums[mid]) r = mid - 1;
            else l = mid + 1;
        } else {                               // right half is sorted
            if (nums[mid] < target && target <= nums[r]) l = mid + 1;
            else r = mid - 1;
        }
    }
    return -1;
}

# python - the generic "sort once, lower-bound each query" shape
# time = O(n log n) build + O(log n) per query, space = O(n)
import bisect

pairs = sorted((v, i) for i, v in enumerate(raw))   # NOTE !!! pair value WITH original idx
keys  = [v for v, _ in pairs]                       # bisect needs a plain sorted list

j = bisect.bisect_left(keys, x)                     # first value >= x
ans = pairs[j][1] if j < len(keys) else -1          # map sorted pos -> original idx

// java - the same query, hand-rolled (identical to findLeft in the template below)
// time = O(log N), space = O(1)
private int lowerBound(int[] keys, int x) {
    int l = 0, r = keys.length - 1;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (keys[mid] < x) l = mid + 1;   // strict < → equality falls right, pushing l left
        else r = mid - 1;
    }
    return l;                              // l == keys.length → no value >= x
}

Monotonic stack : for each i, the FIRST element to its LEFT / RIGHT that is > (or <) nums[i]
                  -> a POSITIONAL neighbour; array order is the whole point

Lower bound     : for each query x, the SMALLEST value >= x in the WHOLE set
                  -> a VALUE ranking; position is irrelevant, so sort first

current.end
     ↓
all intervals' starts (sorted)
     ↓
first start >= end          → lower bound

nums = [5, 7, 7, 8, 8, 10],  target = 8

  [ < target ] [ == target ] [ > target ]
   5  7  7       8  8          10
   0  1  2       3  4          5
                 ^  ^
              first  last

after findLeft :  everything left of l is  < target   → l = first index >= target
after findRight:  everything right of r is > target   → r = last  index <= target

target present  → l = first equal idx, r = last equal idx  → l <= r  ✅
target absent   → both searches collapse to the same gap:
                  l = insertion point p,  r = p - 1        → l >  r  ❌ return [-1,-1]

findLeft(nums, target)  ==  bisect.bisect_left(nums, target)       # count of elements < target
findRight(nums, target) ==  bisect.bisect_right(nums, target) - 1  # count of elements <= target, minus 1

# python - LC 34 Find First and Last Position of Element in Sorted Array
# IDEA: two binary searches — left boundary + right boundary
# time = O(log N), space = O(1)
class Solution:
    def searchRange(self, nums, target):
        l = self.findLeft(nums, target)
        r = self.findRight(nums, target)
        # NOTE !!! l <= r is the existence check (no nums[] lookup needed)
        return [l, r] if l <= r else [-1, -1]

    def findLeft(self, nums, target):
        l, r = 0, len(nums) - 1
        while l <= r:
            mid = l + (r - l) // 2
            # NOTE !!! strict `<` → equality falls to else → keep pushing LEFT
            if nums[mid] < target:
                l = mid + 1
            else:
                r = mid - 1
        return l   # NOTE !!! return l

    def findRight(self, nums, target):
        l, r = 0, len(nums) - 1
        while l <= r:
            mid = l + (r - l) // 2
            # NOTE !!! `<=` → equality goes into if → keep pushing RIGHT
            if nums[mid] <= target:
                l = mid + 1
            else:
                r = mid - 1
        return r   # NOTE !!! return r

// java - LC 34 Find First and Last Position of Element in Sorted Array
// IDEA: two binary searches — left boundary + right boundary
// time = O(log N), space = O(1)
public int[] searchRange(int[] nums, int target) {
    int l = findLeft(nums, target);
    int r = findRight(nums, target);
    return l <= r ? new int[]{l, r} : new int[]{-1, -1};
}

private int findLeft(int[] nums, int target) {
    int l = 0, r = nums.length - 1;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (nums[mid] < target) l = mid + 1;   // strict <
        else r = mid - 1;
    }
    return l;
}

private int findRight(int[] nums, int target) {
    int l = 0, r = nums.length - 1;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (nums[mid] <= target) l = mid + 1;  // <= (the only difference)
        else r = mid - 1;
    }
    return r;
}

# python - LC 34, half-open boundary [lo, hi)
# time = O(log N), space = O(1)
class Solution:
    def searchRange(self, nums, target):
        def search(x):
            """first index i where nums[i] >= x  (== bisect_left)"""
            lo, hi = 0, len(nums)          # NOTE: hi = len(nums), NOT len-1
            while lo < hi:
                mid = (lo + hi) // 2
                if nums[mid] < x:
                    lo = mid + 1
                else:
                    hi = mid               # NOTE: no -1 (half-open)
            return lo

        lo = search(target)
        hi = search(target + 1) - 1        # last idx of target = first idx of target+1, minus 1
        return [lo, hi] if lo <= hi else [-1, -1]

# python - LC 34, explicit "record then keep searching"
# time = O(log N), space = O(1)
class Solution:
    def searchRange(self, nums, target):
        def find_bound(is_first):
            l, r = 0, len(nums) - 1
            bound = -1
            while l <= r:
                mid = l + (r - l) // 2
                if nums[mid] == target:
                    bound = mid                      # record candidate
                    if is_first:
                        r = mid - 1                  # DON'T return — keep going left
                    else:
                        l = mid + 1                  # keep going right
                elif nums[mid] < target:
                    l = mid + 1
                else:
                    r = mid - 1
            return bound

        left = find_bound(True)
        if left == -1:                               # early exit: target absent
            return [-1, -1]
        return [left, find_bound(False)]

# python - LC 34 via bisect
# time = O(log N), space = O(1)
import bisect
class Solution:
    def searchRange(self, nums, target):
        left = bisect.bisect_left(nums, target)
        if left >= len(nums) or nums[left] != target:
            return [-1, -1]
        return [left, bisect.bisect_right(nums, target) - 1]

findLeft (strict <, return l):
  l=0 r=5  mid=2  nums[2]=7 <  8  → l=3
  l=3 r=5  mid=4  nums[4]=8 !< 8  → r=3
  l=3 r=3  mid=3  nums[3]=8 !< 8  → r=2
  l=3 > r=2 → exit, return l=3          ✓ first index of 8

findRight (<=, return r):
  l=0 r=5  mid=2  nums[2]=7 <= 8  → l=3
  l=3 r=5  mid=4  nums[4]=8 <= 8  → l=5
  l=5 r=5  mid=5  nums[5]=10 > 8  → r=4
  l=5 > r=4 → exit, return r=4          ✓ last index of 8

l=3 <= r=4 → [3, 4] ✓

findLeft  → l = 1   (insertion point)
findRight → r = 0   (= insertion point - 1)
l=1 > r=0 → [-1, -1] ✓

# python - LC 300 Longest Increasing Subsequence, O(n log n)
# IDEA: tails[k] = the SMALLEST tail value among increasing subsequences of length k+1
#       -> tails is sorted -> lower-bound it (findLeft, §1.3) -> append or overwrite
# time = O(n log n), space = O(n)
class Solution(object):
    def lengthOfLIS(self, nums):
        # tails[k] : smallest possible ending value of an increasing run of length k + 1
        tails = []

        for num in nums:
            # NOTE !!! this IS findLeft from §1.3, run on `tails` instead of on `nums`
            l, r = 0, len(tails) - 1
            while l <= r:
                mid = l + (r - l) // 2
                if tails[mid] < num:
                    l = mid + 1      # strict < -> equality fails this test, so it
                                     # takes the else and pushes r left
                else:
                    r = mid - 1
            # l == lower_bound(tails, num) == first index with tails[l] >= num

            if l == len(tails):
                tails.append(num)    # num beats every tail -> a NEW longest length exists
            else:
                tails[l] = num       # same length, cheaper tail -> overwrite

        return len(tails)            # NOTE !!! the LENGTH is the answer, not the contents

tails:   [ tails[0] ... tails[l-1] | tails[l] ... ]
           <  num  (extendable)      >= num
                          ^ longest extendable run has length l
                            -> num is a candidate tail for length l + 1 -> slot l

nums  = [3, 4, 5, 1]
tails = [1, 4, 5]     <- 1 sits at index 0 but arrives LAST in the input
len   = 3             <- correct: the LIS is [3,4,5]

// 1) while (l <= r) - CLOSED BOUNDARY [l, r]
while (l <= r) {
    int mid = l + (r - l) / 2;
    if (nums[mid] == target) return mid;
    else if (nums[mid] < target) l = mid + 1;  // MUST +1
    else r = mid - 1;                          // MUST -1
}
// Pros: Standard, easy to understand
// Cons: Can return -1 if not found

// 2) while (l < r) - HALF-OPEN [l, r)
while (l < r) {
    int mid = l + (r - l) / 2;
    if (nums[mid] < target) l = mid + 1;       // +1 to exclude mid
    else r = mid;                              // NO -1, keep mid in range
}
// After loop: l == r, points to answer or insertion point
// Pros: Great for finding boundaries, no -1 return
// Cons: Requires different logic for different problems

// 3) while (l < r - 1) - GAP-BASED
while (l < r - 1) {
    int mid = l + (r - l) / 2;
    if (condition(mid)) l = mid;
    else r = mid;
}
// Final check needed: examine both l and r
// Pros: Avoids infinite loops in complex conditions
// Cons: More complex, requires post-processing

// Java Implementation
public int binarySearch(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    
    // Use <= to search when left == right
    while (left <= right) {
        int mid = left + (right - left) / 2;  // Avoid overflow
        
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid + 1;   // Target in right half
        } else {  // nums[mid] > target
            right = mid - 1;  // Target in left half
        }
    }
    return -1;  // Not found
}

# Python Implementation  
def binary_search(nums, target):
    left, right = 0, len(nums) - 1
    
    # Closed boundary [left, right] - includes both endpoints
    while left <= right:
        mid = left + (right - left) // 2  # Avoid overflow
        
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1   # Search right half
        else:
            right = mid - 1  # Search left half
            
    return -1  # Target not found

def sqrt(x: float, precision=1e-9) -> float:
    lo, hi = 0.0, max(1.0, x)
    while hi - lo > precision:
        mid = (lo + hi) / 2
        if mid * mid <= x:
            lo = mid
        else:
            hi = mid
    return lo

# General pattern: binary search on continuous domain
def minimize_real(lo: float, hi: float, iterations=100) -> float:
    for _ in range(iterations):   # fixed iterations avoids float precision issues
        mid = (lo + hi) / 2
        if feasible(mid):
            hi = mid
        else:
            lo = mid
    return (lo + hi) / 2

def searchMatrix(matrix, target):
    m, n = len(matrix), len(matrix[0])
    lo, hi = 0, m * n - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        val = matrix[mid // n][mid % n]
        if val == target: return True
        elif val < target: lo = mid + 1
        else: hi = mid - 1
    return False

def searchMatrix(matrix, target):
    row, col = 0, len(matrix[0]) - 1   # start top-right
    while row < len(matrix) and col >= 0:
        if matrix[row][col] == target: return True
        elif matrix[row][col] > target: col -= 1   # too big → go left
        else: row += 1                             # too small → go down
    return False

// java
// LC 74
// V1
// IDEA : BINARY SEARCH + FLATTEN MATRIX
// https://leetcode.com/problems/search-a-2d-matrix/editorial/
public boolean searchMatrix_2(int[][] matrix, int target) {
    int m = matrix.length;
    if (m == 0)
        return false;
    int n = matrix[0].length;

    // binary search
    /** NOTE !!! FLATTEN MATRIX */
    int left = 0, right = m * n - 1;
    int pivotIdx, pivotElement;
    while (left <= right) {
        pivotIdx = (left + right) / 2;
        /** NOTE !!! TRICK HERE :
         *
         *   pivotIdx / n : y index
         *   pivotIdx % n : x index
         */
        pivotElement = matrix[pivotIdx / n][pivotIdx % n];
        if (target == pivotElement)
            return true;
        else {
            if (target < pivotElement)
                right = pivotIdx - 1;
            else
                left = pivotIdx + 1;
        }
    }
    return false;
}

ascending : nums[mid] < target  -> go RIGHT (l = mid + 1)
descending: nums[mid] > target  -> go RIGHT (l = mid + 1)

probe 1, 2, 4, 8, 16, ...  until the value overshoots the target (or falls off the end)
                           -> the answer is inside [prev probe, this probe]

# python
# LC 702 - Search in a Sorted Array of Unknown Size
# IDEA: double the index until reader.get() overshoots -> that bounds the answer;
#       then run an ordinary binary search inside the window
# time = O(log p) where p is the target's index, space = O(1)
class Solution(object):
    def search(self, reader, target):
        hi = 1
        while reader.get(hi) < target:       # out of range returns 2^31-1, so this stops
            hi <<= 1                         # 1, 2, 4, 8, ... only O(log p) probes
        lo = hi >> 1                         # the previous probe was still < target

        while lo <= hi:
            mid = lo + (hi - lo) // 2
            val = reader.get(mid)
            if val == target:
                return mid
            elif val < target:
                lo = mid + 1
            else:
                hi = mid - 1                 # also the "past the end" case
        return -1

// java
// CtCI 10.4 - search a sorted "Listy" that has no size(); elementAt() returns -1 past the end
// IDEA: same doubling, but the sentinel here is -1, which reads as TOO SMALL —
//       so it has to be tested for explicitly instead of comparing naturally
// time = O(log p), space = O(1)
int search(Listy list, int target) {
    int hi = 1;
    while (list.elementAt(hi) != -1 && list.elementAt(hi) < target) {
        hi *= 2;
    }
    int lo = hi / 2;

    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        int val = list.elementAt(mid);
        if (val == target) return mid;
        if (val == -1 || val > target) hi = mid - 1;   // -1 means past the end -> go left
        else lo = mid + 1;
    }
    return -1;
}

# python
# CtCI 10.5 - find a word in a sorted string array that is padded with "" entries
# IDEA: a probe landing on "" tells you nothing, so walk outward from mid — both
#       directions at once — to the closest real string, then continue normally
# time = O(log n) when holes are sparse, O(n) worst case; space = O(1)
def sparse_search(words, target):
    if not target:                            # "" has no defined position
        return -1
    lo, hi = 0, len(words) - 1

    while lo <= hi:
        mid = lo + (hi - lo) // 2

        if not words[mid]:                    # in a hole: find the nearest word
            left, right = mid - 1, mid + 1
            while True:
                if left < lo and right > hi:
                    return -1                 # this whole window is empty
                elif right <= hi and words[right]:
                    mid = right
                    break
                elif left >= lo and words[left]:
                    mid = left
                    break
                left -= 1
                right += 1

        if words[mid] == target:
            return mid
        elif words[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1