Course 2: binary search and sorted array

二分法

模板：

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

while-loop is better than recursion
关键：每次要去掉一半

二分法Example 1：找第一次出现

Example: Binary search is a famous question in algorithm. For a given sorted array (ascending order) and a target number, find the first index of this number in O(log n) time complexity. If the target number does not exist in the array, return -1. Example If the array is [1, 2, 3, 3, 4, 5, 10], for given target 3, return 2.

class Solution {
    /**
     * @param nums: The integer array.
     * @param target: Target to find.
     * @return: The first position of target. Position starts from 0.
     */
    public int binarySearch(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }

        int start = 0, end = nums.length - 1;


        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            //尽量往左边靠
            if (nums[mid] == target) {
                end = mid;  
            } else if (nums[mid] < target) {
                start = mid;
            } else {
                end = mid;
            }
        }

        //找first occurance，所以先看start
        if (nums[start] == target) {
            return start;
        }
        if (nums[end] == target) {
            return end;
        }
        return -1;
    }
}

注意点：

while条件分析：退出时，不满足start+1= end，相邻就退出，虽然后面还要判断一下，但这种写法通用，不容易死循环
1. start = end - 1
2. start = end
mid = start + (end - start) / 2
start = mid, end = mid：更安全

二分法Example 2：找最后一次出现

if (nums[mid] == target) {start = mid;}

if (nums[end] == target) {
    return end;
}
if (nums[start] == target) {
    return start;
}

More example:

Sorted array

Median of two sorted array: 重要

Recover rotated sorted array

45123->12345
三步翻转法：
45 123
54 321
12345

Rotate String