Rotated and 2-D Array

Find Peak Element:

1. 如何知道哪边才可能出现极值，很大可能是在递增区间
2. 用mid 与 mid + 1来确定哪边是递增区间
3. 黄金分割搜索用求函数极值，二分法用来求函数的根

Find Peak Element II:

左右上下都是出现了峰值的可能，多一个维度的峰值

1. 想法跟前者是一样的，用mid 与 mid + 1来判断走势
2. 可是为何只用一次上下维度的二分查找

Find Minimum in Rotated Sorted Array II：

1. Check current position in left part of right part: nums[mid] < nums[right]
2. Duplicate allowed：nums[mid] == nums[right] → right-- (why not left++)

Search in Rotated Sorted Array II：

1. Check current position in left part of right part: nums[mid] < nums[right]
2. left part:
   1. nums[mid] < target --> left = mid + 1
   2. nums[mid] > target
      1. target < nums[right] --> left = mid + 1
      2. target > nums[right] --> right = mid
3. right part:
   1. nums[mid] > target --> right = mid
   2. nums[mid] < target
      1. target < nums[right] --> left = mid + 1
      2. target > nums[right] --> right = mid

Search a 2D Matrix II

1. start from top right go down and left O(m + n)
2. classic binary search and divide and conquer by divide four blocksO(n^log3)

public boolean searchMatrix(int[][] matrix, int target) {
    if (matrix.length == 0 || matrix[0].length == 0) return false;
    int x = 0, y = matrix[0].length - 1;
    while (y >= 0 && x < matrix.length) {
        if (matrix[x][y] == target) return true;
        if (matrix[x][y] < target) {
            x++;
        } else {
            y--;
        }
    }
    return false;
}