刷题第一篇：二分查找算法

「这是我参与11月更文挑战的第6天，活动详情查看：2021最后一次更文挑战」

前言

今天和大家分享一道简单的算法题，花哥算法不精，期待和小伙伴们多学习学习，在评论区指教一二，明天又要开始搬砖了，划起来。

题目分析

给定一个 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

• 提示：

你可以假设 nums 中的所有元素是不重复的。 n 将在 [1, 10000]之间。 nums 的每个元素都将在 [-9999, 9999]之间。 通过次数322,230提交次数583,055

二分查找的核心思想就是将n个元素分成两部分，然后比较a[n/2] 与 target的大小关系：

1. 如果 x=a[n/2] , 则找到 target , 查找结束中止；
2. 如果 x<a[n/2] , 则只需要在数组 a 的左半部分继续搜索 target；
3. 如果 x>a[n/2] , 则只需要在数组 a 的右半部分继续搜索 target；

代码分析

• 代码示例

public int search(int[] nums, int target) {
    int left = 0;
    int right = nums.length-1;
    while (left <= right){
        int mid =left + ((right - left) >> 1);
        if (target == nums[mid]){
            return mid;
        }else if(target < nums[mid]){
            right = mid-1;
        }else {
            left = mid+1;
        }
    }
    return -1;
}
复制代码

• 首先， mid = (left+ high) /2 。

• 然后比较target与a[mid]值的大小：

  1. 若a[mid] == target ，表示查找成功，此时停止查找；
  2. 若a[mid]> target ，表示给定值target在区间left- mid-1之间，那就要修改查询条件，将right=mid-1，left值不变；
  3. 若a[mid]<target ，表示给定值target在区间mid+1- high之间，那就要修改查询条件，将left=mid+1，right值不变；
  4. 比较当前变量left和right的值，若left≤right，重复前面步骤，若left>right，表示数组中不存在目标元素，返回-1。

注意点

上面代码涉及到临界点，可以看到while中是<=，这主要和right的赋值有关，right=nums.length-1，也就是到数组最后一个元素的的索引位置，相当于闭区间【left,right】。

(right - left) >> 1：相当于(rigth-left)/2。

\