Leetcode代码复盘_分治法相关

 分治法

1.二分搜索（算法时间复杂度O(log n)）

输出：如果x=A[j],则输出j，否则输出0.
     1.binarysearch(1,n)
过程：binarysearch(low,high)

        1.if low>high then return 0
        2.else
        3.        mid←(low+high)/2
        4.        if x=A[mid]     then return mid
        5.        else if x<A[mid]  then return binarysearch(low,mid-1)
        6.        else return  binarysearch(mid+1,high)
        7.end if

Leetcode NO33  搜索旋转数组

class Solution {
    public int search(int[] nums, int target) {
        int lo = 0;
        int hi = nums.length - 1;

        while (lo < hi) {
            int mid = (lo + hi) / 2;
            // 当[0,mid]有序时,向后规约条件
            if (nums[0] <= nums[mid] && (target > nums[mid] || target < nums[0])) {
                lo = mid + 1;
                // 当[0,mid]发生旋转时，向后规约条件
            } else if (target > nums[mid] && target < nums[0]) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        return lo == hi && nums[lo] == target ? lo : -1;
    }
}