LeetCode 704. 二分查找

题目链接：

力扣https://leetcode-cn.com/problems/binary-search/

【分析】二分查找的模板题，写二分查找时记住以下几个点就很好写了：

1.start = 0, end = n - 1;

2.mid = (start + end) / 2;

3.判定继续的条件为while(start <= end);

4.缩短区间通过start = mid + 1, end = mid - 1来实现。

【非递归实现】

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

【递归实现】

class Solution {
    public int binarySearch(int nums[], int start, int end, int target){
        if(start > end) return -1;
        int mid = (start + end) / 2;
        if(nums[mid] == target) return mid;
        else if(nums[mid] > target) return binarySearch(nums, start, mid - 1, target);
        else return binarySearch(nums, mid + 1, end, target);
    }

    public int search(int[] nums, int target) {
        return binarySearch(nums, 0, nums.length - 1, target);
    }
}