二分查找及其延伸

1.基本概念

二分查找就是将查找的键和子数组的中间键作比较，如果被查找的键小于中间键，就在左子数组继续查找；如果大于中间键，就在右子数组中查找，否则中间键就是要找的元素。
递归法

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

非递归法

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

2. Find Minimum in Rotated Sorted Array（Leetcode153）

有序旋转数组寻找最小值

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
Find the minimum element.
You may assume no duplicate exists in the array.
思路：

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

3. Search in Rotated Sorted Array（Leetcode 33）

有序旋转数组里寻找固定的一个值

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
Find the minimum element.
You may assume no duplicate exists in the array.

思路：

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