LeetCode:二分查找

题目

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

提示：

1. 你可以假设 nums 中的所有元素是不重复的。
2. n 将在 [1, 10000]之间。
3. nums 的每个元素都将在 [-9999, 9999]之间。

分析

对于有序数组的查找，一个方便快捷的方法就是二分查找。
不停的找中间的那个值跟我们的目标值比较。
如下图：
比如我们要查找的值是9，返回其下标5。
根据二分查找的思想，我们第一轮搜索的下标范围是[0,6]，找到的中间元素是下标为3的元素4,目标值9比4大，则下一轮我们要搜索的下标范围是[4,6]，这个时候找到的中间元素是下标为5的元素9，发现正是我们要找的目标值，搜索结束。

注意：在写代码的时候，我们要注意搜索范围的边界。
搜索范围的区间的定义一般为两种，左闭右闭即[left, right]，或者左闭右开即[left, right)

①区间范围[left, right]

区间范围[left, right]说明我们在搜索的时候左右区间都能取到。

• while (left <= right) 要使用 <= ，因为left == right是有意义的，所以使用 <=
• if (nums[middle] > target) right 要赋值为 middle - 1，因为当前这个nums[middle]一定不是target，那么接下来要查找的左区间结束下标位置就是 middle - 1

代码（C语言）：

int search(int* nums, int numsSize, int target){
    int left,right,mid;
    left=0;
    right=numsSize-1;
    while(left<=right){
        mid=floor((left+right)/2);
        if(target>nums[mid]){
            left=mid+1;
        }else if(target<nums[mid]){
            right=mid-1;
        }else{
            return mid;
        }
    }
    return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

②区间范围[left, right)

区间范围[left, right)在搜索的时候只能取到左边的区间。

• while (left < right)，这里使用 < ,因为left == right在区间[left, right)是没有意义的
• if (nums[middle] > target) right 更新为 middle，因为当前nums[middle]不等于target，去左区间继续寻找，而寻找区间是左闭右开区间，所以right更新为middle，即：下一个查询区间不会去比较nums[middle]

代码（C语言）：

int search(int* nums, int numsSize, int target){
    int left,right,mid;
    left=0;
    right=numsSize;
    while(left<right){
        mid=floor((left+right)/2);
        if(target>nums[mid]){
            left=mid+1;
        }else if(target<nums[mid]){
            right=mid;
        }else{
            return mid;
        }
    }
    return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

虽然只是微小的差别，请各位细细琢磨！！！