1/31, 二分位置

二分搜索本质上就是一个不断去缩小搜索范围的过程，目的是保留有解的那一半。
二分通过O(1)的时间把规模为n的问题分为n/2，所以时间复杂度是O(lgn)。
二分的前提是sorted array。
规范一下binary search的变量名，low , high (对比two pointer 的 left , right)

先用一道classic题复习下解决这类问题的思路和模板。

Classical Binary Search

Find any position of a target number in a sorted array，这个target会在array里出现多次，返回任意一个位置就行。

public class Solution {
    public int findPosition(int[] nums, int target) {
        // write your code here
        if (nums == null || nums.length == 0) return -1;

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

首先要注意while循环的跳出条件，left+1 < right，也就是说当left + 1 = right时跳出，这也是为什么后面要对left和right分别判断，因为二分的目的是去缩小找到正解的范围，而不是直接return答案。

第二，在while循环内部，没有把else归入elif的情况，原因是这部分的判断要根据题目而定，固定了反而会出错。

另一处细节是用left + (right - left) // 2计算中点位置，而不是直接(left + right) // 2，因为后者可能造integer overflow，如果input是很大的数组的话。

Search for a Range

找一个target在array里出现的start和ending position，其实就是用到上面的第二点，二分的方向是往左还是往右有利于找到解。

class Solution {
    public int[] searchRange(int[] nums, int target) {
        if (nums == null || nums.length == 0) return new int[]{-1, -1};

        int low = 0, high = nums.length - 1;
        int leftIndex = low, rightIndex = high;
        while (low + 1 < high) {
            int mid = low + (high - low) / 2;
            if (nums[mid] < target) {
                low = mid;
            } else if (nums[mid] > target) {
                high = mid;
            } else {
                high = mid;
            }
        }

        if (nums[low] == target) leftIndex = low;
        else if (nums[high] == target) leftIndex = high;
        else leftIndex = -1;

        low = 0;
        high = nums.length - 1;
        while (low + 1 < high) {
            int mid = low + (high - low) / 2;
            if (nums[mid] < target) {
                low = mid;
            } else if (nums[mid] > target) {
                high = mid;
            } else {
                low = mid;
            }
        }

        if (nums[high] == target) rightIndex = high;
        else if (nums[low] == target) rightIndex = low;
        else rightIndex = -1;

        return new int[]{leftIndex, rightIndex};
    }
}

和要找insert/last position还是target的total occurrence类似。

Search Insert Position

easy, 但是不要忘记最后有一个if 语句，if (target > nums[right]) return right + 1;

class Solution {
    public int searchInsert(int[] nums, int target) {
        if (nums == null || nums.length == 0) return 0;

        int low = 0, high = nums.length - 1;
        while (low + 1 < high) {
            int mid = low + (high - low) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                low = mid;
            } else {
                high = mid;
            }
        }

        if (target <= nums[low]) return low;
        if (target <= nums[high]) return high;
        if (target > nums[high]) return high + 1;

        return 0;
    }
}

Find Minimum in Rotated Sorted Array

二分的高频题之一，target未知。利用了单调性。

class Solution {
    public int findMin(int[] nums) {
        if (nums == null || nums.length == 0) return 0;

        int n = nums.length;
        int low = 0, high = n - 1;
        int target = nums[high];
        while (low + 1 < high) {
            int mid = low + (high - low) / 2;
            if (nums[mid] < target) {
                high = mid;
            } else if (nums[mid] > target) {
                low = mid;
            } else {
                high = mid;
            }
        }
        return Math.min(nums[low], nums[high]);
    }
}

记住找minimum用尾巴作target，找maximum用head。

这题还有一种可能，就是array包含duplicates。如果再上一题进行修改，可以讲nums[mid] == target 情况 right--; 因为你不知道最小值在左边还是右边。或者可以事先从末尾删除所有与nums[0]相同的值，或者最简单直接for一下，没必要用二分，因为二分时间复杂度也是O(n)，而且重点也不是写二分，而是能不能想到duplicates的情况。

1/27，记得有一题求rotated times，其实是一回事，最小下标可以用来得到次数。

Search in Rotated Sorted Array

这题的思路是解决二分这类问题的关键，一定要通过严格的条件限制去二分区间。

class Solution {
    public int search(int[] nums, int target) {
        if (nums == null || nums.length == 0) return -1;

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

        return -1;
    }
}
The positions of target == nums[right] and target == nums[left] are critical in both branches 
due to this test:
[5,1,3] target:3 
lo:(0), hi:(2)
lo:(0), hi:(0)
[5 1 3 ] and 5 -> 0, expected: 0

凡是rotated的，都可利用端点。先定mid位置，再定target区间。

1/27再刷，画图，利用target可能出现的位置来讨论，注意边界一定要严格划分。

另一个思路是，我们可以利用之前那一题的思路来确定搜索区间。pay attention to Arrays.binarySearch()的使用

Arrays.binarySearch()

method signature is int binarySearch(int[] a, int fromIndex, int toIndex, int key)
fromIndex is the index of the first element (inclusive), while toIndex is the index of the first element (exclusive)

class Solution {
    public int search(int[] nums, int target) {
        if (nums == null || nums.length == 0) return -1;

        int n = nums.length;
        int minIndex = findMinNum(nums);
        if (nums[minIndex] <= target && nums[n - 1] >= target) {
            int index = Arrays.binarySearch(nums, minIndex, nums.length, target);
            if (index < 0) return -1;
            return index;
        }
        else if (nums[0] <= target && (minIndex > 0 && nums[minIndex - 1] >= target)) {
            int index = Arrays.binarySearch(nums, 0, minIndex, target);
            if (index < 0) return -1;
            return index;
        }
        return -1;
    }

    private int findMinNum(int[] nums) {
        int low = 0, high = nums.length - 1;
        int target = nums[high];
        while (low + 1 < high) {
            int mid = low + (high - low) / 2;
            if (nums[mid] < target) {
                high = mid;
            } else if (nums[mid] > target) {
                low = mid;
            } else {
                high = mid;
            }
        }
        if (nums[low] < nums[high]) {
            return low;
        }
        return high;
    }
}

Search in Rotated Sorted Array II

这题的Array存在duplicates，所以考虑到最坏情况在[1,1,1,1,1,1,1,0,1,1,1,....1]找0，二分在sorted array上的时间复杂度是O(lgn)，这里是O(n)，不如直接用for循环，也是O(n)。类似find minimum in rotated sorted array，二分不是这题的考点。

class Solution {
    public boolean search(int[] nums, int target) {
        if (nums == null || nums.length == 0) return false;
        int n = nums.length;
        for (int i = 0; i < n; ++i) {
            if (nums[i] == target) {
                return true;
            }
        }
        return false;
    }
}

如果遇到此类rotated sorted题目时，一定要和面试官make sure if array contain duplicates。

另一个思路是我们可以去除array末尾或者开头的duplicates。

class Solution {
    public boolean search(int[] nums, int target) {
        if (nums == null || nums.length == 0) return false;

        int n = nums.length;
        int low = 0, high = n - 1;
        while (low < high && nums[low] == nums[high]) {
            high--;
        }

        while (low + 1 < high) {
            int mid = low + (high - low) / 2;
            if ((nums[mid] > nums[high] && target >= nums[low] && target <= nums[mid]) ||
                (nums[mid] <= nums[high] && !(target >= nums[mid] && target <= nums[high]))) {
                high = mid;
            } else {
                low = mid;
            }
        }
        if (nums[low] == target) return true;
        if (nums[high] == target) return true;
        return false;
    }
}

Search a 2D Matrix 2

在2D array里找一个target，array满足两条件，每行都是sorted，每行第一个数比前一行最后一个大。可以看成一个1D array来做。

solution 1:

We start search the matrix from top right corner, initialize the current position to top right corner, if the target is greater than the value in current position, then the target can not be in entire row of current position because the row is sorted, if the target is less than the value in current position, then the target can not in the entire column because the column is sorted too. We can rule out one row or one column each time, so the time complexity is O(m+n). space: O(1)

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;

        int n = matrix.length;
        int m = matrix[0].length;

        int row = 0, col = m - 1;
        while (row < n && col >= 0) {
            if (matrix[row][col] > target) {
                col--;
            } else if (matrix[row][col] < target) {
                row++;
            } else {
                return true;
            }
        }
        return false;
    }
}

solution 2: using binary search (optional)

every time I search for current row and current column. So the time complexity is O(log(n!)) < O(n log(n))

class Solution {
    private boolean binarySearch(int[][] matrix, int target, int start, boolean vertical) {
        int lo = start;
        int hi = vertical ? matrix[0].length-1 : matrix.length-1;

        while (hi >= lo) {
            int mid = (lo + hi)/2;
            if (vertical) { // searching a column
                if (matrix[start][mid] < target) {
                    lo = mid + 1;
                } else if (matrix[start][mid] > target) {
                    hi = mid - 1;
                } else {
                    return true;
                }
            } else { // searching a row
                if (matrix[mid][start] < target) {
                    lo = mid + 1;
                } else if (matrix[mid][start] > target) {
                    hi = mid - 1;
                } else {
                    return true;
                }
            }
        }
        return false;
    }

    public boolean searchMatrix(int[][] matrix, int target) {
        // an empty matrix obviously does not contain `target`
        if (matrix == null || matrix.length == 0) {
            return false;
        }

        // iterate over matrix diagonals
        int shorterDim = Math.min(matrix.length, matrix[0].length);
        for (int i = 0; i < shorterDim; i++) {
            boolean verticalFound = binarySearch(matrix, target, i, true);
            boolean horizontalFound = binarySearch(matrix, target, i, false);
            if (verticalFound || horizontalFound) {
                return true;
            }
        }

        return false; 
    }
}

Find Peak Element

找到array中任一个peak position，peak point满足A[p] > A[p-1] and A[p] > A[p+1]。array is unsorted，但在某个区间一定是递增or递减的。low + 1 < high, 所以必然array至少有三个数才会走while循环，所以不用考虑mid - 1, mid + 1越界情况。

class Solution {
    public int findPeakElement(int[] nums) {
        if (nums == null || nums.length == 0) return 0;

        int low = 0, high = nums.length - 1;
        while (low + 1 < high) {
            int mid = low + (high - low) / 2;
            if (nums[mid] > nums[mid - 1] && nums[mid] < nums[mid + 1]) {
                low = mid;
            } else if (nums[mid] < nums[mid - 1] && nums[mid] > nums[mid + 1]) {
                high = mid;
            } else {
                high = mid; // pay attention: try to find the leftmost peak element. 
            }
        }
        if (nums[low] > nums[high]) return low;  // so consider the low element first
        if (nums[low] < nums[high]) return high;

        return 0;
    }
}

refer peak element 2 -> matrix 上找峰值怎么办？思考🤔

关键在于，用当前行/列最大值的位置，代表整行或列。在“山峰”问题里，一个一维数组里，山峰的位置取决于里面的最大值，或局部最大值;在二维矩阵里，一行的max决定了这行所能达到的最高高度，在和相邻元素进行比较时，相邻元素若比max大，则max所属的行列，就饿一定可以做为新的padding边界，把这种单调性传递下去。

public class Solution {

    public List<Integer> findPeakII(int[][] A) {
        // write your code
        if (A == null || A.length == 0 || A[0].length == 0) return new ArrayList<>();

        List<Integer> list = new ArrayList<>();
        int left = 1, right = A[0].length - 2;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int index = getColMaxIndex(A, mid);
            if (A[index][mid] < A[index][mid - 1]) {
                right = mid - 1;
            } else if (A[index][mid] < A[index][mid + 1]) {
                left = mid + 1;
            } else {
                list.add(index);
                list.add(mid);
                return list;
            }
        }
        return list;
    }

    private int getColMaxIndex(int[][] A, int col) {
        int index = 0;
        int max = A[0][col];
        for (int i = 1; i < A.length - 1; ++i) {
            if (A[i][col] > max) {
                max = A[i][col];
                index = i;
            }
        }
        return index;
    }
}

Search in a Big Sorted Array

array很大长度未知，二分是需要知道搜索边界的，要利用给的函数try to access some position，先得到右边界。倍增的思想

public class Solution {

    public int searchBigSortedArray(ArrayReader reader, int target) {
        // write your code here
        int index = 0;
        while (reader.get(index) != -1 && reader.get(index) < target) {
            index = index * 2 + 1;
        }

        int low = 0, high = index;
        while (low + 1 < high) {
            int mid = low + (high - low) / 2;
            if (reader.get(mid) < target) {
                low = mid;
            } else if (reader.get(mid) > target) {
                high = mid;
            } else {
                high = mid;
            }
        }
        if (reader.get(low) == target) return low;
        if (reader.get(high) == target) return high;

        return -1;
    }
}

用reader.get()得到一个approximate scan range (0, index)，时间复杂度是O(lgk)，k是length of array。

二分位置