需要牢记的二分法基础模板

public class BasicBinarySearch {
    public static void main(String[] args) {
        int[] nums = {1,3,5,7,10,13,18};
        System.out.println("数字所在位置：" + searchNum(nums, 18));
    }

    private static int searchNum(int[] nums, int target) {
        if (nums == null || nums.length == 0){
            return -1;
        }
        int start = 0;
        int end = nums.length -1;
        int middle;
        //记住这里，为什么不用start<=end而用start + 1 < end，因为start + (end-start)/2会取不到最左边的数18
        while (start + 1 < end){
            middle = start + (end-start)/2;
            if (target < nums[middle]){
                end = middle;
            } else if (target > nums[middle]){
                start = middle;
            } else {
                return middle;
            }
        }
        if (target == nums[start]) {
            return start;
        } else if (target == nums[end]) {
            return end;
        } else {
            return -1;
        }
    }
}

搜索旋转排序数组

click here for leetcode detail

class Solution {
    public int search(int[] nums, int target) {
        if (nums == null || nums.length == 0){
            return -1;
        }
        int start = 0;
        int end = nums.length - 1;
        int middle;
        while (start + 1 < end){
            middle = start + (end -start)/2;
            if (nums[middle] == target){
                return middle;
            }
            //解题思路：不管怎么旋转，都可以把nums看成前后递增的两端，只用通过nums[middle]
            //和nums[start]就可以判断target是在二分的前半部分还是后半部分。
            //这里需要注意
            if (nums[middle] > nums[start]){
                //这里需要注意
                if (target <= nums[middle] && target >= nums[start]){
                    end = middle;
                } else {
                    start = middle;
                }
            } else {
                if ( target >= nums[middle] && target <= nums[end]){
                    start = middle;
                } else {
                    end = middle;
                }
            }
        }
        if(nums[start] == target){
            return start;
        }
        if(nums[end] == target){
            return end;
        }
        return -1;
    }
}

找旋转排序数组中的最小值

click here for leetcode detail

class Solution {
    public int findMin(int[] nums) {
        if (nums == null || nums.length == 0){
            return -1;
        }
        int start = 0;
        int end = nums.length - 1;
        int mid = -1;
        while(start + 1 < end){
            mid = start + (end - start)/2;
            if (nums[mid] > nums[end]){
                start = mid;
            } else {
                end = mid;
            }
        }
        return nums[start] < nums[end] ? nums[start] : nums[end];
    }
}

寻找峰值

click here for leetcode detail

示意图

class Solution {
    public int findPeakElement(int[] nums) {
        if ( nums == null || nums.length < 2){
            return 0;
        }
        int start = 0;
        int end = nums.length - 1;
        int mid;
        while(start + 1 < end){
            mid = start + (end - start)/2;
            //下峰
            if (nums[mid] < nums[mid -1]){
                end = mid;
            //上峰
            } else if (nums[mid] < nums[mid + 1]){
                start = mid;
            } else {
                return mid;
            }
        }
        return nums[start] > nums[end] ? start : end;
    }
}