文章目录

• 一、题目描述
• 二、解题步骤
• • 1.思路
  • 2.代码
  • 3.复杂度分析
• 三、总结

一、题目描述

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

前提条件：1、数组有序；2、数组元素不重复。

其他题目中满足这两个前提，可以看看能不能使用二分法。

思路讲解：在定义的区间范围内寻找目标值target，中间值nums[mid]和target进行比较。中间值等于目标值，返回下标；若大于目标值，说明目标值在左半边区间；若小于目标值，说明目标值在右半边区间。这种方式可以让搜索空间不断减半。

细节难点：虽然二分法思路较为简单，但是细节却是拉满！！！

1、在while(…)中到底什么时候是left<right,什么时候是left<=right?
2、区间减半时，什么时候right=mid+1,什么时候直接right=mid?

这些细节都建立在区间的确立上，首先区间有两种形式，左闭右闭[left,right]，还有一种是左闭右开[left,right)。下面我们来看一下两种区间定义的区别。

细节1、while循环什么时候退出，当然是在区间为空时退出。我们使用左闭右闭区间（[left,right]）时，当出现[2,2]时，明显还有一个值2可取，所以写成while(left<=right)。而在左闭又开（[left,right)）区间时，[2,2)明显是不会存在值的，所以直接使用while(left<right)。
细节2、如果理解了上面的区间，那么接下来的内容就更好理解了，在第一次查询时nums[mid]不能和target匹配，缩减区间。在左开右闭[left,right]区间内，nums[mid]已经匹配过了，不可能是target值，所以，我们查询区间不用去包括它，所以right=mid-1（或left=mid+1)进行区间缩小；在左闭右开区间[left,right)，right=mid，因为右区间为开区间，本来就不能匹配到，而left=mid+1,左区间是闭区间，匹配后不能成功，就不用将数据加入到数组中。

总结：所有细节都是根据区间性质，所以确定区间不变，其他规则都需要和区间性质一一对应。

2.代码

左闭有闭区间[left,right]：

class Solution {    public int search(int[] nums, int target) { int i=0; int j=nums.length-1; while(i<=j){ //细节1     int mid = i + ((j-i) >> 1);//不使用(i+j)>>1，是因为相加可能超出最大整数范围     if(nums[mid]==target){  return mid;     }else if(nums[mid]>target){  j=mid-1;//细节2     }else if(nums[mid]<target){  i=mid+1;     } }   return -1;    }}

左闭右开区间[left,right)

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

3.复杂度分析

时间复杂度：O(logn)
空间复杂度：O(1)

三、总结

二分查找是最基础的查找算法之一，都是其中也有好几个需要注意的细节，自己在做题的时候可能不会去注意，然后调试调试着才提交成功了，通过写这边博客让自己对二分查找通透了。

造句网