Binary Search

https://leetcode.com/discuss/general-discussion/786126/python-powerful-ultimate-binary-search-template-solved-many-problems

704. Binary Search

Java

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

Python

278. First Bad Version

Find first "T" in the array, when meet the situation below, still move L pointer:

# F F F T T T

# [1, 2, 10, 11.., n]

    def firstBadVersion(self, n):
        L = 1
        R = n
        while L < R:
            mid = (L + R) // 2
            if isBadVersion(mid) :
                R = mid
            else: 
                L = mid + 1
        return L

162. Find Peak Element & 852. Peak Index in a Mountain Array

when nums[mid] > nums[mid - 1] means it is on upslope, move L pointer. Otherwise move R pointer.

def findPeakElement(self, nums: List[int]) -> int:
    L = 0
    R = len(nums)
    while L < R:
        mid = (L + R) // 2
        if mid < len(nums) - 1 and nums[mid + 1] >= nums[mid]:
            L = mid + 1
        else :
            R = mid
    return L

34. Find First and Last Position of Element in Sorted Array

Find the first position and the last position separately. Treat differently as nums[mid] == target

public int[] searchRange(int[] nums, int target) {
    if (nums == null || nums.length == 0 || target > nums[nums.length - 1]) {
        return new int[]{-1, -1};
    }
    int left = binarySearchFirst(nums, 0, nums.length - 1, target);
    int right = binarySearchLast(nums, 0, nums.length - 1, target);
    return left == -1 ? new int[]{-1, -1} : new int[]{left, right};
}

private int binarySearchFirst(int[] nums, int left, int right, int target) {
    while (left + 1 < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] >= target) {
            right = mid;
        } else {
            left = mid;
        }
    }
    if (nums[left] == target) return left;
    if (nums[right] == target) return right;
    return -1;
}

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

33. Search in Rotated Sorted Array

Use right most digit as a pivot to determine if mid is on the lower side or the higher side, then determine the position of target to move the pointers.

def search(self, nums: List[int], target: int) -> int:
    if len(nums) == 0:
        return -1
    L = 0
    R = len(nums) - 1
    pivot = nums[R]
    
    while L + 1 < R:
        mid = (L + R) // 2
        if nums[mid] <= pivot:
            if target <= pivot and target >= nums[mid]:
                L = mid
            else :
                R = mid
        else :
            if target > pivot and target < nums[mid]:
                R = mid
            else:
                L = mid
    if nums[L] == target :
        return L
    if nums[R] == target:
        return R
    return -1

81. Search in Rotated Sorted Array II

When nums[mid] == nums[L] and nums[mid] == nums[R] means all three pointers are on same level. Compare target vs nums[R], check if nums[mid] is in between, or on the opposite side.

def search(self, nums: List[int], target: int) -> bool:
    L = 0
    R = len(nums) - 1
    if len(nums) == 0:
        return False
    while L + 1 < R:
        mid = (L + R) // 2
        if nums[mid] == target:
            return True
        if nums[mid] == nums[L] and nums[mid] == nums[R]:
            L += 1
            R -= 1
        elif target <= nums[R]:
            if nums[mid] > target and nums[mid] <= nums[R]:
                R = mid
            else:
                L = mid
        else:
            if nums[mid] < target and nums[mid] > nums[R]:
                L = mid
            else:
                R = mid
    if nums[L] == target or nums[R] == target:
        return True
    return False

153. Find Minimum in Rotated Sorted Array

Use right most element as pivot to determine the direction of the search. If nums[mid] less and equal to pivot, then move R to mid. Otherwise move L to mid.

    def findMin(self, nums: List[int]) -> int:
        L = 0
        R = len(nums) - 1
        pivot = nums[len(nums) - 1]
        while L + 1 < R:
            mid = (L + R) // 2
            if nums[mid] > pivot:
                L = mid
            else:
                R = mid
        return min(nums[L], nums[R])

702. Search in a Sorted Array of Unknown Size

Define boundaries by expanding right pointer. To keep logarithmic time complexity, let's extend it twice as far: right = right * 2. Then binary search.

    def search(self, reader, target):
        R = 1
        while reader.get(R) <= target:
            R *= 2
        L = 0
        while L + 1 < R:
            mid = (L + R) // 2
            if reader.get(mid) == target:
                return mid
            if reader.get(mid) < target:
                L = mid
            else:
                R = mid
        if reader.get(L) == target:
            return L
        if reader.get(R) == target:
            return R
        return -1

Another solution (if getNumber() API is provided):

  public boolean binarysearch(long target) {
    long start = 0;
    long end = 1;
    while (getNumber(end) <= target && end < Long.MAX_VALUE / 2) {
      end *= 2;
    }
    if (getNumber(end) < target) {
      end = Long.MAX_VALUE;
    }
    while (start + 1 < end) {
      long mid = start + (end - start) / 2;
      if (getNumber(mid) == target) {
        return true;
      } else if (getNumber(mid) < target) {
        start = mid;
      } else {
        end = mid;
      }
    }
    return getNumber(start) == target || getNumber(end) == target;
  }

50. Pow(x, n)

2 ^ 10 = 4 ^ 5 = 16 ^ 2 * 4

T: O(logn) S: O(1)

    public double myPow(double x, int n) {
        if (n == 0) return 1.0;
        if (n == 1) return x;
        int i = Math.abs(n);
        double res = 1.0;
        while (i != 0) {
            if (i % 2 != 0) {
                res *= x; 
            }
            x *= x;
            i /= 2;
        }
        return n < 0 ? 1.0 / res : res;
    }

540. Single Element in a Sorted Array

For example, in [1,1,3,3,4,4,5,8,8], elements before 5 keep [even, odd] pattern, to make sure that even and odd number sequence. The elements after 5 break this sequence. In this case, we can determine the target is on the left or the right side of pivot.

    def singleNonDuplicate(self, nums: List[int]) -> int:
        L = 0
        R = len(nums) - 1
        while L < R:
            mid = (L + R) // 2
            if mid % 2 == 0 and mid < len(nums) - 1 and nums[mid + 1] == nums[mid]:
                L = mid + 1
            elif mid % 2 == 1 and mid > 0 and nums[mid - 1] == nums[mid]:
                L = mid + 1
            else:
                R = mid
        return nums[L]

1060. Missing Element in Sorted Array

nums[mid] - nums[left] is the number difference on array, mid - leftis the difference of indices. The difference diff between those two numbers can give you how close are we reaching out to k.

The k needs to decrement by diff when moving left pointer, as k is from the beginning.

The result is nums[left] + k. However the number may exceed right so the result is nums[left] + k + 1 in that situation.

    public int missingElement(int[] nums, int k) {
        int left = 0, right = nums.length - 1;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            int diff = nums[mid] - nums[left] - (mid - left);
            if (diff < k) {
                left = mid;
                k -= diff;
            } else {
                right = mid;
            }
        }
        if (nums[left] + k >= nums[right]) return nums[left] + k + 1;
        return nums[left] + k;
    }

300. Longest Increasing Subsequence

dp is an array storing the smallest tail of all increasing subsequences with length i+1 in dp[i]. For example, say we have nums = [4,5,6,3], then all the available increasing subsequences are:

• len = 1 : [4], [5], [6], [3] => tails[0] = 3

• len = 2 : [4, 5], [5, 6] => tails[1] = 5

• len = 3 : [4, 5, 6] => tails[2] = 6

We can easily prove that tails is a increasing array. Therefore it is possible to do a binary search in tails array to find the one needs update.

Each time we only do one of the two:

• if x is larger than all tails, append it, increase the size by 1

• if dp[i-1] < x <= dp[i], update dp[i]

T: O(nlogn)

public int lengthOfLIS(int[] nums) {
    int n = nums.length;
    int[] res = new int[n];
    int size = 0;
    for (int num : nums) {
        int L = 0, R = size;
        while (L < R) {
            int mid = L + (R - L) / 2;
            if (res[mid] < num) {
                L = mid + 1;
            } else {
                R = mid;
            }
        }
        res[L] = num;
        if (L == size) size++;
    }
    return size;
}

911. Online Election

Count the votes and derive the winner that that time. When querying, store the results in a TreeMap to get the results. Otherwise we can store by using an array and use binary search to find the answer.

TreeMap

TreeMap<Integer, Integer> results;
public TopVotedCandidate(int[] persons, int[] times) {
    Map<Integer, Integer> votes = new HashMap<>();
    results = new TreeMap<>();
    int n = persons.length;
    int max = 0, maxperson = -1;
    for (int i = 0; i < n; i++) {
        votes.put(persons[i], votes.getOrDefault(persons[i], 0) + 1);
        if (votes.get(persons[i]) >= max) {
            max = votes.get(persons[i]);
            maxperson = persons[i];
        }
        results.put(times[i], maxperson);
    }
}

public int q(int t) {
    int key = results.get(t) != null ? t
                                     : results.lowerKey(t);
    return results.get(key);
}

Binary Search

528. Random Pick with Weight

Store the array to prefix sum and randomly get an integer between range 0 and max. Use binary search to get the index of that integer is presum.

int[] w;
Random rand;
public Solution(int[] w) {
    this.w = w;
    for (int i = 1; i < w.length; i++) {
        w[i] += w[i - 1];
    }
    this.rand = new Random();
}

public int pickIndex() {
    int index = rand.nextInt(w[w.length - 1]) + 1;
    int L = 0, R = w.length - 1;
    while (L < R) {
        int mid = L + (R - L) / 2;
        if (w[mid] == index) return mid;
        if (w[mid] < index) {
            L = mid + 1;
        } else {
            R = mid;
        }
    }
    return L;
}

4. Median of Two Sorted Arrays

We can use Binary Search to find a median of two sorted array. The index i in the first array has to follow this relation as i + j = (len1 + len2) / 2 (Actually it is i + j - 1= (len1 + len2 + 1) / 2). Therefore, use binary search to find the position which nums1[i] >= nums2[j - 1].

You will have i, j. Before return, determine if any of the indices are out of bound. Keep the boundary elements by choosing one value between i and j. If is odd total length, only pick one element as median, otherwise get the average of those two boundary elements.

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int len1 = nums1.length, len2 = nums2.length;
    if (len1 > len2) return findMedianSortedArrays(nums2, nums1);
    int len = (len1 + len2 + 1) / 2;
    int left = 0, right = len1;
    while (left < right) {
        int m1 = left + (right - left) / 2;
        int m2 = len - m1;
        if (nums1[m1] < nums2[m2 - 1]) {
            left = m1 + 1;
        } else {
            right = m1;
        }
    }
    int m1 = left, m2 = len - m1;
    int c1 = Math.max(m1 <= 0 ? Integer.MIN_VALUE : nums1[m1 - 1],
                      m2 <= 0 ? Integer.MIN_VALUE : nums2[m2 - 1]);
    if ((len1 + len2) % 2 == 1) return c1;
    int c2 = Math.min(m1 >= len1 ? Integer.MAX_VALUE : nums1[m1],
                      m2 >= len2 ? Integer.MAX_VALUE : nums2[m2]);
    return (c1 + c2) / 2.0;
}

1095. Find in Mountain Array

3 binary searches

public int findInMountainArray(int target, MountainArray A) {
    int left = 0, right = A.length() - 1;
    // Find the peak index
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (A.get(mid) < A.get(mid + 1)) {
            left = mid + 1;
        } else { 
            right = mid;
        }
    }
    int peak = left;
    
    // Binary search on increasing subarray
    left = 0;
    right = peak;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (A.get(mid) < target) {
            left = mid + 1;
        } else if (A.get(mid) > target) { 
            right = mid - 1;
        } else {
            return mid;
        }
    }
    
    // Binary search on decreasing subarray
    left = peak;
    right = A.length() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (A.get(mid) < target) {
            right = mid - 1;
        } else if (A.get(mid) > target) { 
            left = mid + 1;
        } else {
            return mid;
        }
    }
    return -1;
}

Binary Searchable Elements

Binary search is a search algorithm usually used on a sorted sequence to quickly find an element with a given value. In this problem we will evaluate how binary search performs on data that isn't necessarily sorted. An element is said to be binary searchable if an element can be found provided the pivot is chosen everytime as the middle element - like in a regular binary search. We need to find total number of elements which are binary searchable.

Example 1:

[2, 1, 3, 4, 6, 5] - 3 is searchable, 2 is searchable, 1 not searchable, 6 is searchable, 4 is seachable, 5 is not searchable

Output: 4

Example 2:

Input: [1, 3, 2]

Output: 2

Explanation: 3 and 1 are searchable - you look for 3 - find it in the middle, look for 1 - you search the left half....search for 2, you look for it in the left half but didn't find.

Pretend the array is a binary search tree, DFS/BFS all pivot elements and keep track of lower and upper bound for the left and right children. The idea is to figure out how many middle elements in the given start to end range is properly positioned compared to previous middle element - so that they can be binary searchable in the given array.

public int getSearchableCount(int[] arr) {
    if (arr == null || arr.length == 0) {
        return 0;
    }
    return getSearchableCount(arr, 0, arr.length-1, Integer.MIN_VALUE, Integer.MAX_VALUE);
}

private int getSearchableCount(int[] arr, int start, int end, int lowerBound, int upperBound) {
    if (start > end) {
        return 0;
    }
    int mid = (start + end) / 2;
    int count = 0;
    if (arr[mid] >= lowerBound && arr[mid] <= upperBound) count ++;
    return count + getSearchableCount(arr, start, mid-1, lowerBound, Math.min(arr[mid], upperBound)) +
            getSearchableCount(arr, mid + 1, end, Math.max(arr[mid], lowerBound), upperBound);
}

public static void main(String[] args) {
    BinarySearchable obj = new BinarySearchable();
    System.out.println(obj.getSearchableCount(new int[]{2, 1, 3, 4, 6, 5}));
    System.out.println(obj.getSearchableCount(new int[]{1, 3, 2}));
    System.out.println(obj.getSearchableCount(new int[]{1, 2, 2, 3}));
    System.out.println(obj.getSearchableCount(new int[]{4, 9, 5, 1, 1}));
}

3453. Separate Squares I

function separateSquares(squares: number[][]): number {
  let lo: number = Number.POSITIVE_INFINITY; // initial lower bound
  let hi: number = Number.NEGATIVE_INFINITY; // initial upper bound

  for (const [x, y, l] of squares) {
    lo = Math.min(lo, y - l);
    hi = Math.max(hi, y + l);
  }

  const eps: number = 1e-5; // tolerance level

  while (hi - lo > eps) {
    const mid = (lo + hi) / 2;
    if (isAboveLine(mid, squares)) {
      lo = mid;
    } else {
      hi = mid;
    }
  }

  return (lo + hi) / 2;
}

function isAboveLine(line: number, squares: number[][]): boolean {
  let above = 0;
  let below = 0;

  for (const [x, y, l] of squares) {
    const top = y + l;
    if (line <= y) {
      // Entire square above line
      above += l * l;
    } else if (line >= top) {
      // Entire square below line
      below += l * l;
    } else {
      // Partial square, line cuts inside square
      const heightAbove = top - line;
      const heightBelow = line - y;
      above += heightAbove * l;
      below += heightBelow * l;
    }
  }

  return above > below;
}