二分搜尋

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

// java
// LC 35 - Search Insert Position
// IDEA: Template 1 unchanged; on a miss the exit position l is the insert position
// time = O(log n), space = O(1)
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;
    }
    // ...
}

# python
# LC 704 - Binary Search
# IDEA: closed window [left, right]; drop mid and the half that cannot hold target
# time = O(log n), space = O(1)
def search(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:                      # <= : a one-element window is still a candidate
        mid = left + (right - left) // 2      # // : an int index, never a float
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1                    # nums[..mid] are all < target
        else:
            right = mid - 1                   # nums[mid..] are all > target
    return -1                                 # window empty; left is the insert position

// java
// LC 704 - Binary Search
// IDEA: closed window [left, right]; drop mid and the half that cannot hold target
// time = O(log n), space = O(1)
public int search(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;  // no overflow, unlike (left + right) / 2
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

nums = [-1, 0, 3, 5, 9, 12], target = 9
left right mid nums[mid]  action
0    5     2   3          3 < 9  -> left = 3
3    5     4   9          found  -> return 4

target = 2 (absent)
0    5     2   3          3 > 2  -> right = 1
0    1     0   -1         -1 < 2 -> left = 1
1    1     1   0          0 < 2  -> left = 2
left = 2 > right = 1 -> return -1   (left = 2 is the insert position, LC 35)

# python
# LC 34 - Find First and Last Position of Element in Sorted Array
# IDEA: two partition searches; the one-character difference (< vs <=) decides
#       which way equality falls, and first <= last is the existence check
# time = O(log n), space = O(1)
class Solution(object):
    def searchRange(self, nums, target):
        first = self.findLeft(nums, target)
        last = self.findRight(nums, target)
        if first <= last:                     # absent -> both land in the same gap, first = last + 1
            return [first, last]
        return [-1, -1]

    def findLeft(self, nums, target):
        """first index with nums[i] >= target  (== bisect_left)"""
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] < target:            # strict < : equality goes to else, pushes right leftwards
                left = mid + 1
            else:
                right = mid - 1
        return left

    def findRight(self, nums, target):
        """last index with nums[i] <= target  (== bisect_right - 1)"""
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] <= target:           # <= : equality goes to if, pushes left rightwards
                left = mid + 1
            else:
                right = mid - 1
        return right

// java
// LC 34 - Find First and Last Position of Element in Sorted Array
// IDEA: two partition searches, differing only in < vs <=
// time = O(log n), space = O(1)
public int[] searchRange(int[] nums, int target) {
    int first = findLeft(nums, target);
    int last = findRight(nums, target);
    return first <= last ? new int[]{first, last} : new int[]{-1, -1};
}

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

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

nums = [5, 7, 7, 8, 8, 10], target = 8
findLeft (strict <, return left):
  l=0 r=5  mid=2  7 <  8  -> l=3
  l=3 r=5  mid=4  8 !< 8  -> r=3
  l=3 r=3  mid=3  8 !< 8  -> r=2
  exit, return l=3          first index of 8
findRight (<=, return right):
  l=0 r=5  mid=2  7 <= 8  -> l=3
  l=3 r=5  mid=4  8 <= 8  -> l=5
  l=5 r=5  mid=5  10 > 8  -> r=4
  exit, return r=4          last index of 8
3 <= 4 -> [3, 4]

target = 6 (absent): findLeft -> 1, findRight -> 0, 1 > 0 -> [-1, -1]

# python - the generic "sort once, lower-bound each query" shape
# IDEA: sort (value, original index) pairs once, then one bisect_left per query
# time = O(n log n) build + O(log n) per query, space = O(n)
import bisect

def first_at_least(raw, queries):
    pairs = sorted((v, i) for i, v in enumerate(raw))   # keep each value WITH its original index
    keys = [v for v, _ in pairs]                        # bisect needs a plain sorted list
    answers = []
    for x in queries:
        j = bisect.bisect_left(keys, x)                 # first value >= x
        answers.append(pairs[j][1] if j < len(keys) else -1)   # sorted position -> original index
    return answers

// java - the same query, hand-rolled (identical to findLeft in the template above)
// IDEA: strict < pushes equality left, so l ends on the first key >= x
// 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, half-open boundary [lo, hi)
# IDEA: one bisect_left helper; last of target = first of target + 1, minus 1
# 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"
# IDEA: on a match record mid as the bound, then keep searching toward that side
# 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
# IDEA: bisect_left / bisect_right are findLeft and findRight + 1
# 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]

count of x in [lo, hi]  =  (# elements <= hi)  -  (# elements < lo)          # O(log N)
                        =  bisect_right(xs, hi) - bisect_left(xs, lo)
                        =  lower_bound(xs, hi + 1) - lower_bound(xs, lo)   # integers only

"how often does value v appear in arr[left..right]?"
    -> the indices of v form a sorted list
    -> the question becomes "how many of those indices fall in [left, right]?"
    -> two bound queries on that list

arr      = [12, 33, 4, 56, 22, 2, 34, 33, 22, 12, 34, 56]
index      0   1   2  3   4   5  6   7   8   9   10  11

positions[33] = [1, 7]          positions[22] = [4, 8]

query(0, 11, 33):  bisect_right([1,7], 11) = 2   (both indices <= 11)
                   bisect_left ([1,7],  0) = 0   (no index  <  0)
                   -> 2 - 0 = 2 ✓

query(5, 7, 22):   bisect_right([4,8], 7)  = 1   (4 <= 7, 8 > 7)
                   bisect_left ([4,8], 5)  = 1   (4 <  5)
                   -> 1 - 1 = 0 ✓   (index 4 is before the range, index 8 is after it)

# python
# LC 2080 - Range Frequency Queries
# IDEA: value -> sorted list of its indices (built in one scan),
#       then count the indices inside [left, right] with two bound queries
# time = O(n) build, O(log n) per query, space = O(n)
import bisect
from collections import defaultdict

class RangeFreqQuery(object):

    def __init__(self, arr):
        # value -> every index it appears at; appended left to right, so already sorted
        self.positions = defaultdict(list)
        for idx, val in enumerate(arr):
            self.positions[val].append(idx)

    def query(self, left, right, value):
        # `in` check first, so the defaultdict does not grow an empty list per miss
        if value not in self.positions:
            return 0
        idx_list = self.positions[value]

        start = bisect.bisect_left(idx_list, left)    # first index >= left
        end = bisect.bisect_right(idx_list, right)    # first index >  right
        # idx_list[start:end] are exactly the indices in [left, right]
        return end - start

// java
// LC 2080 - Range Frequency Queries
// IDEA: same lists; one hand-rolled lowerBound, called with left and right + 1
// time = O(n) build, O(log n) per query, space = O(n)
class RangeFreqQuery {
    private final Map<Integer, List<Integer>> positions = new HashMap<>();

    public RangeFreqQuery(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            positions.computeIfAbsent(arr[i], k -> new ArrayList<>()).add(i);
        }
    }

    public int query(int left, int right, int value) {
        List<Integer> idx = positions.get(value);
        if (idx == null) {
            return 0;
        }
        // right + 1 turns "<= right" into "< right + 1", so one helper serves both ends
        return lowerBound(idx, right + 1) - lowerBound(idx, left);
    }

    /** first position whose index is >= target (half-open [l, r), == bisect_left) */
    private int lowerBound(List<Integer> idx, int target) {
        int l = 0, r = idx.size();
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (idx.get(mid) < target) l = mid + 1;
            else r = mid;
        }
        return l;
    }
}

# python
# LC 153 - Find Minimum in Rotated Sorted Array
# IDEA: closed squeeze [left, right] down to one candidate; nums[right] tells which run mid is in
# time = O(log n), space = O(1)
def findMin(nums):
    left, right = 0, len(nums) - 1
    while left < right:                       # stop at one candidate, not zero
        mid = left + (right - left) // 2
        if nums[mid] < nums[right]:
            right = mid                       # mid..right ascending: min is mid or left of it
        else:
            left = mid + 1                    # mid is in the high run: min is right of mid
    return nums[left]

// java
// LC 153 - Find Minimum in Rotated Sorted Array
// IDEA: closed squeeze [left, right] down to one candidate; nums[right] tells which run mid is in
// time = O(log n), 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;       // keep mid: it may be the minimum
        } else {
            left = mid + 1;
        }
    }
    return nums[left];
}

nums = [3, 4, 5, 1, 2]
left right mid nums[mid] nums[right]  action
0    4     2   5         2            5 >= 2 -> left = 3
3    4     3   1         2            1 < 2  -> right = 3
left == right = 3 -> return 1

// java
// LC 153 - Find Minimum in Rotated Sorted Array (closed boundary, track ans)
// IDEA: a sorted window's minimum is its left end; otherwise record mid and move to the unsorted half
// 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) {
        if (nums[l] <= nums[r]) {             // window already sorted -> minimum is at l
            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 -> the drop is to the right
        } else {
            r = mid - 1;                      // right plateau -> mid recorded, look left
        }
    }
    return ans;
}

Rotation examples (length 5) and where the template moves:
[1, 2, 3, 4, 5]  -> mid < right -> right = mid ... min at index 0
[5, 1, 2, 3, 4]  -> mid < right -> right = mid
[3, 4, 5, 1, 2]  -> mid > right -> left = mid + 1
[2, 3, 4, 5, 1]  -> mid > right -> left = mid + 1

# python
# LC 33 - Search in Rotated Sorted Array
# IDEA: one half of [left, mid, right] is always sorted; keep it iff target lies between its ends
# time = O(log n), space = O(1)
def search(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            return mid
        if nums[left] <= nums[mid]:                    # left half nums[left..mid] is sorted
            if nums[left] <= target < nums[mid]:
                right = mid - 1                        # target inside the sorted left half
            else:
                left = mid + 1
        else:                                          # right half nums[mid..right] is sorted
            if nums[mid] < target <= nums[right]:
                left = mid + 1                         # target inside the sorted right half
            else:
                right = mid - 1
    return -1

// java
// LC 33 - Search in Rotated Sorted Array
// IDEA: one half is always sorted; keep it iff target lies between its ends
// time = O(log n), space = O(1)
public int search(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) return mid;
        if (nums[left] <= nums[mid]) {                 // left half is sorted
            if (nums[left] <= target && target < nums[mid]) right = mid - 1;
            else left = mid + 1;
        } else {                                       // right half is sorted
            if (nums[mid] < target && target <= nums[right]) left = mid + 1;
            else right = mid - 1;
        }
    }
    return -1;
}

nums = [4, 5, 6, 7, 0, 1, 2], target = 0
left right mid nums[mid]  sorted half       target inside?  action
0    6     3   7          left [4..7]       no              left = 4
4    6     5   1          left [0..1]       0 <= 0 < 1 yes  right = 4
4    4     4   0          found -> return 4

# 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, Template 2) -> append or overwrite
# time = O(n log n), space = O(n)
class Solution(object):
    def lengthOfLIS(self, nums):
        tails = []
        for num in nums:
            # findLeft from Template 2, run on `tails` instead of on `nums`
            left, right = 0, len(tails) - 1
            while left <= right:
                mid = left + (right - left) // 2
                if tails[mid] < num:
                    left = mid + 1           # strict < : an equal tail is replaced, not extended
                else:
                    right = mid - 1
            # left == first index with tails[left] >= num
            if left == len(tails):
                tails.append(num)            # num beats every tail -> a new longest length
            else:
                tails[left] = num            # same length, cheaper tail -> overwrite
        return len(tails)                    # the LENGTH is the answer, not the contents

// java
// LC 300 - Longest Increasing Subsequence, O(n log n)
// IDEA: tails[0..size) is strictly increasing; lower-bound each num into it, overwrite or append
// time = O(n log n), space = O(n)
public int lengthOfLIS(int[] nums) {
    int[] tails = new int[nums.length];
    int size = 0;
    for (int num : nums) {
        int left = 0, right = size - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (tails[mid] < num) left = mid + 1;
            else right = mid - 1;
        }
        tails[left] = num;                // left == size appends, otherwise overwrites
        if (left == size) size++;
    }
    return size;
}

nums = [10, 9, 2, 5, 3, 7, 101, 18]
num   lower bound   action        tails
10    0 (empty)     append        [10]
9     0             overwrite     [9]
2     0             overwrite     [2]
5     1             append        [2, 5]
3     1             overwrite     [2, 3]
7     2             append        [2, 3, 7]
101   3             append        [2, 3, 7, 101]
18    3             overwrite     [2, 3, 7, 18]     -> 4

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

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
# `feasible` is your monotone predicate: False on [lo, x*), True on [x*, hi]
def minimize_real(lo: float, hi: float, feasible, 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

# python
# LC 74 - Search a 2D Matrix
# IDEA: Template 1 on the virtual flat array; flat index i -> matrix[i // n][i % n]
# time = O(log(m * n)), space = O(1)
def searchMatrix(matrix, target):
    m, n = len(matrix), len(matrix[0])
    left, right = 0, m * n - 1
    while left <= right:
        mid = left + (right - left) // 2
        value = matrix[mid // n][mid % n]     # divide by the column count, not the row count
        if value == target:
            return True
        elif value < target:
            left = mid + 1
        else:
            right = mid - 1
    return False

// java
// LC 74 - Search a 2D Matrix
// IDEA: Template 1 on the virtual flat array; flat index i -> matrix[i / n][i % n]
// time = O(log(m * n)), space = O(1)
public boolean searchMatrix(int[][] matrix, int target) {
    int m = matrix.length, n = matrix[0].length;
    int left = 0, right = m * n - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        int value = matrix[mid / n][mid % n];
        if (value == target) return true;
        else if (value < target) left = mid + 1;
        else right = mid - 1;
    }
    return false;
}

# python
# LC 240 - Search a 2D Matrix II
# IDEA: from the top-right, a larger value rules out its column and a smaller one its row
# time = O(m + n), space = O(1)
def searchMatrixII(matrix, target):
    row, col = 0, len(matrix[0]) - 1
    while row < len(matrix) and col >= 0:
        if matrix[row][col] == target:
            return True
        elif matrix[row][col] > target:
            col -= 1                          # everything below in this column is bigger too
        else:
            row += 1                          # everything left in this row is smaller too
    return False

# python
# LC 162 - Find Peak Element
# IDEA: closed squeeze down to one candidate; move toward the higher neighbour of mid, which always holds a peak
# time = O(log n), space = O(1)
def findPeakElement(nums):
    left, right = 0, len(nums) - 1
    while left < right:                       # left < right, so mid + 1 is always in range
        mid = left + (right - left) // 2
        if nums[mid] < nums[mid + 1]:
            left = mid + 1                    # rising slope: a peak is to the right
        else:
            right = mid                       # falling slope: mid itself may be the peak
    return left

// java
// LC 162 - Find Peak Element
// IDEA: closed squeeze down to one candidate; move toward the higher neighbour of mid
// time = O(log n), space = O(1)
public int findPeakElement(int[] nums) {
    int left = 0, right = nums.length - 1;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < nums[mid + 1]) left = mid + 1;
        else right = mid;
    }
    return left;
}

nums = [1, 2, 1, 3, 5, 6, 4]
left right mid  nums[mid] vs nums[mid+1]   action
0    6     3    3 < 5                      left = 4
4    6     5    6 > 4                      right = 5
4    5     4    5 < 6                      left = 5
left == right = 5 -> return 5   (6 is a peak; index 1 would also be accepted)

ascending : nums[mid] < target  -> go RIGHT (left = mid + 1)
descending: nums[mid] > target  -> go RIGHT (left = 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
// LC 702 - Search in a Sorted Array of Unknown Size
// IDEA: double hi until reader.get(hi) >= target, then Template 1 inside [hi / 2, hi]
// time = O(log p), space = O(1)
public int search(ArrayReader reader, int target) {
    int hi = 1;
    while (reader.get(hi) < target) {        // the 2^31-1 sentinel past the end stops this
        hi *= 2;
    }
    int lo = hi / 2;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        int val = reader.get(mid);
        if (val == target) return mid;
        else if (val < target) lo = mid + 1;
        else hi = mid - 1;                   // a sentinel reads as "too big": go left
    }
    return -1;
}

# python
# LC 702 - Search in a Sorted Array of Unknown Size (lower-bound variant)
# IDEA: double hi until get(hi) >= target, then find the FIRST index in [hi // 2, hi]
#       whose value is >= target; the target exists iff that index holds it
# 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:
            hi *= 2

        lo = hi // 2                          # get(lo) < target, or lo == 0
        while lo < hi:
            mid = (lo + hi) // 2
            if reader.get(mid) >= target:     # sentinel 2^31-1 also lands here -> go left
                hi = mid
            else:
                lo = mid + 1

        return lo if reader.get(lo) == target else -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