Binary Search

经典二分搜索及其变种

二分搜索的核心思想是，在给定的搜索空间内，排除掉一定不对的那一部分。应用场景往往是有序的，或者局部有序的。这样从 $O(n)$ 可以优化到 $O(logn)$. 搜索空间的定义可以是具体的值，也可以是数组的索引，需要具体问题具体分析。

Classic binary search

  int classic_binary_search(vector<int> input, int target) {
    if (input.empty()) {
      return -1;
    }
    int left = 0;
    int right = input.size() - 1;
    while (left <= right){
      int mid = left + (right - left)/2;
      if (input[mid] == target){
        return mid;
      }
      else if (input[mid] < target) {
        left = mid + 1;
      }
      else {
        right = mid - 1;
      }
    }
    return -1;
  }
};

find last/first index of target

  int find_first_index(vector<int> input, int target) {
    if (input.size() == 0) return -1;
    int left = 0, right = input.size() - 1;
    while (left < right - 1){
      int mid = left + (right - left)/2;
      if (target > input[mid]){
        left = mid;
      }
      else {
        right = mid;
      }
    }

    if (input[left] == target){
      return left;
    }
    else if (input[right] == target) {
      return right;
    }
    else
      return -1;
  }

  int find_last_index(vector<int> input, int target) {
    if (input.empty())  {
      return -1;
    }
    int left = 0;
    int right = input.size() - 1;
    while (left < right - 1){
      int mid = left + (right - left)/2;
      if (target >= input[mid]){
        left = mid;
      }
      else {
        right = mid;
      }
    }

    if (input[right] == target) {
      return right;
    }
    else if (input[left] == target) {
      return left;
    }
    else {
      return -1;
    }
  }

Search in a sorted array of unknown size

Given an integer array sorted in ascending order, write a function to search target in nums. If target exists, then return its index, otherwise return -1. However, the array size is unknown to you. You may only access the array using an ArrayReader interface, where ArrayReader.get(k) returns the element of the array at index k (0-indexed).

You may assume all integers in the array are less than 10000, and if you access the array out of bounds, ArrayReader.get will return 2147483647.

Example 1: Input: array = [-1,0,3,5,9,12], target = 9 Output: 4 Explanation: 9 exists in nums and its index is 4

Example 2: Input: array = [-1,0,3,5,9,12], target = 2 Output: -1 Explanation: 2 does not exist in nums so return -1 Note:

You may assume that all elements in the array are unique. The value of each element in the array will be in the range [-9999, 9999].

class Solution {
public:
    int search(const ArrayReader& reader, int target) {
        int prev = 0, cur = 1;
        while (prev < cur) {
            long k = reader.get(cur);
            if (k == target) {
               return cur; 
            }
            else if (k < target) {
                prev = cur;
                cur = cur * 2;
            } else {
                cur = (prev + cur) / 2;                 
            }
        }
        return reader.get(0) == target? 0 : -1;
    }
};

二维二分搜索

Search a 2D Matrix

Problem Link from Leetcode

从左到右递增，下一行的开头一定比上一行的末尾大。那么就可以转化为一维的二分搜索。考点在二维矩阵到一维矩阵的变换。

bool searchMatrix(vector<vector<int>>& matrix, int target) {
  int left = 0;
  int right = matrix.size() * matrix[0].size() - 1;
  while (left <= right) {
    int mid = left + (right - left) / 2;
    int i = mid / matrix[0].size();
    int j = mid % matrix[0].size();
    if (matrix[i][j] == target) {
      return true;
    } else if (target > matrix[i][j]) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  return false;
}

Search a 2D matrix II

Problem Link from Leetcode

从左往右一定递增，从上到下一定递增。跟之前一题相比，这里的二维矩阵并不能保证转化成一维递增的矩阵。如果从左上角开始往右下角搜索，那么有多种可能，刚开始用的是分治法，把矩阵分成四块，由于这个矩形的性质，我们只能排除掉一块，然后往三块可能的继续搜。时间复杂度为$O(n^{1.58})$, 参考分治法时间复杂度分析公式. 但如果从右上角往左下角搜，那么可以保证向左一定是递减的，向下一定是递增的，那么可以排除掉特定行或者特定列。这样的时间复杂度出来的是$O(m + n)$.

bool searchMatrix(vector<vector<int>>& matrix, int target) {
	int m = matrix.size();
	if (m == 0) return false;
	int n = matrix[0].size();
	int i = 0, j = n - 1;
	while (i < m && j >= 0) {
		if (matrix[i][j] == target)
			return true;
		else if (matrix[i][j] > target) {
			j--;
		} else
			i++;
	}
	return false;
}

Binary search in rotated array

Find Minimum in Rotated Sorted Array

Duplication allowed

// 5 1 1 2 2 2 3 4
class Solution {
public:
    int findMin(vector<int>& nums) {
        int left = 0;
        int right = nums.size() - 1;
        while (left < right - 1) {
            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 min(nums[left], nums[right]);
    }
};

Find Minimum in Rotated Sorted Array
Find Minimum in Rotated Sorted Array II
Search in Rotated Sorted Array II

Binary search to solve Kth problem

Find Kth smallest/largest number in two sorted array

class Solution {
public:
    double findMedianSortedArrays(vector<int>& a, vector<int>& b) {
        int N = a.size() + b.size();
        //return (findKthSmallest(a, b, 0, 0, (N + 1)/2) + findKthSmallest(a, b, 0, 0, (N + 2)/2)) / 2.0;
        return (findKthLargest(a, b, a.size() - 1, b.size() - 1, (N + 1)/2) + findKthLargest(a, b, a.size() - 1, b.size() - 1, (N + 2)/2)) / 2.0;

    }
    
    int findKthLargest(const vector<int> & a, const vector<int> & b, int a_right, int b_right, int k) {        
        if (a_right < 0) {
            return b[b_right - k + 1];
        }
        if (b_right < 0) {
            return a[a_right - k + 1];
        }
        if (k == 1) {
            return max(a[a_right], b[b_right]);
        }        
        int p = (a_right - k/2 + 1 >= 0) ? a[a_right - k/2 + 1] : INT_MIN;
        int q = (b_right - k/2 + 1 >= 0) ? b[b_right - k/2 + 1] : INT_MIN;

        if (p >= q) {
            return findKthLargest(a, b, a_right - k/2, b_right, k - k/2);
        }
        else {
            return findKthLargest(a, b, a_right, b_right - k/2, k - k/2);
        }
    }
    
    int findKthSmallest(const vector<int> & a, const vector<int> & b, int a_left, int b_left, int k) {
        if (a_left == a.size()) {
            return b[b_left + k - 1];
        } 
        if (b_left == b.size()) {
            return a[a_left + k - 1];
        }
        if (k == 1) {
            return min(a[a_left], b[b_left]);
        }
        // p: half kth smallest in array a
        int p = (a_left + k/2 - 1) < a.size()? a[a_left + k/2 - 1] : INT_MAX;
        // q: half kth smallest in array a
        int q = (b_left + k/2 - 1) < b.size()? b[b_left + k/2 - 1] : INT_MAX;
        
        //discard 
        if (p < q) {    
            return findKthSmallest(a, b, a_left + k/2, b_left, k - k/2);
        } else {
            return findKthSmallest(a, b, a_left, b_left + k/2, k - k/2);
        }
    }
};

Reference: https://www.geeksforgeeks.org/k-th-element-two-sorted-arrays/

Follow up: find Kth smallest element in m sorted arrays

Find Kth smallest element in a sorted matrix

https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/

class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        return helper(matrix, k, matrix.front().front(), matrix.back().back());   
    }
    
    int helper(const vector<vector<int>>& matrix, int k, int left, int right) {
        if (left >= right) {
            return left;
        }
        //pick a reference value
        int mid = left + (right - left)/2;
        int n = matrix.size(); 
        int m = 0;
        //counts number of elements smaller than or equal to mid
        for (int i = 0; i < n; i++) {
                          
            /* 
             * 
             *The upper bound idea if optimized from:
              for (int j = 0; j < matrix[i].size(); j++) {
                  if (matrix[i][j] <= mid) {
                      m++;
                  }
              }
             * using for loop is the basic idea to help understand,
             * actually we can use binary search again to find the smallest element that larger than mid
             */            

            int num = upper_bound(matrix[i].begin(), matrix[i].end(), mid) - matrix[i].begin();
            m += num;
        }
        // now we know that there are m elements <= mid[include mid]
        // thus mid is m th smallest element in the matrix
        // if m == k, actually mid is the kth 
        // if m < k, then kth smallest element must appear after mid
        // otherwise, kth element must appear before mid

        if (m < k) {
            return helper(matrix, k, mid + 1, right);
        } else {
            return helper(matrix, k, left, mid);
        }
    }
};

Dynamic programming and binary search

Longest Increasing Subsequence

Russian Doll Envelopes

浮点类型

浮点类型往往需要引入最小收敛精度，当搜索空间越来越小知道逼近到这个精度的时候停止搜索。不要乱加这个精度，不要乱加这个精度，不要乱加这个精度。

Calculate Square Root

Here is a very intuitive binary search solution.

double sqrt(const double number) {
    const double e = 1.0e-7;
    double left, right, guess;
    
    if (number < 1) {
        left = number;
        right = 1;
    }
    else {
        left = 1;
        right = number;
    }
    
    while ((right - left) > e) {
        guess = left + (right - left) / 2;
        if (guess > number / guess) {
            right = guess;
        }
        else {
            left = guess;
        }
    }
    return left + (right - left) / 2;
}

According to Newton–Raphson method,

$$ x_{n+1} = x_n - \frac{f(x_n)}{f’(x_n)}$$

Here $f(x_n) = {x_n}^2 - S = 0$, so we can deduce that，

$$x_{n+1} = x_n - \frac{f(x_n)}{f’(x_n)} = x_n - \frac{{x_n}^2 - S}{2x_n} = \frac{1}{2}(x_n + \frac{S}{x_n})$$

Based on this induction rule, we can do a binary search in the space.

double sqrt(const double num) {
    const double e = 1.0e-7;
    double guess = num / 2;
    while (abs(guess * guess - num) > e) {
        guess = (guess + num / guess) / 2;
    }
    return guess;
}

Calculate pow(x, n)

class Solution {
public:
    double myPow(double x, int n) {
        if (n < 0) {
            return 1.0 / helper(x, -n);
        } else {
            return helper(x , n); 
        }
    }
    
    double helper(double x, int n) {
        if (n == 0) {
            return 1;
        }
        double v = helper(x, n / 2);
        //return (n % 2 == 0)? helper(x, n / 2) * helper(x, n / 2) : helper(x, n / 2) * helper(x, n / 2) * x;
        return (n % 2 == 0)? v * v : v * v * x;
    }
};

Reference: Best Square Root Method