vlambda博客
学习文章列表

让我们先看看这道题目的描述

分析：

这道题目的题目已经在明示我们使用二分了。

二分的代码很简单，但是其中有几个细节需要注意。

细节一：mid到底取（left + right) >> 1 还是（left + right + 1) >> 1?

我们在二分的题目中，经常看到这两种写法都会存在，到底有什么区别呢？

情况一：（left + right) >> 1  

这种情况对应着left = mid + 1， 或者 right = mid ，意味着从左方向逼近

情况二：（left + right + 1) >> 1  

这种情况对应着left = mid， 或者 right = mid - 1，意味着从右方向逼近

具体的想法可以用只有两个元素的数组进行简单模拟。

细节二：while里面到底取< 还是 <= ?

这两种写法都特别常见。

我个人更倾向于取<符号的写法，因为这样结束循环的时候一定满足left == right，而不用考虑left和right的关系

细节三：以（left + right) >> 1  为🌰，到底写（left + right） / 2，还是

（left + right）>> 1 还是left + （right - left）/ 2 ？

情况一：（left + right） / 2 这种情况会存在int溢出的风险，不推荐

情况二：（left + right）>> 1这种情况的底层是进行移位操作，同样存在int溢出的风险，不推荐

情况三：left + （right - left）/ 2  推荐。

由于这道题目的数据量范围不是很大，所以我还是选择了第二种写法。

方法一：

class Solution{ public int search(int[] nums, int target) { int left = 0; int right = nums.length - 1; while(left < right ){ int mid = (left + right ) >> 1; if(nums[mid] < target) left = mid + 1; else right = mid; } return nums[left] == target ? left : - 1; }}

方法二：

class Solution{ public int search(int[] nums, int target) { int left = 0; int right = nums.length - 1; while(left < right ){ int mid = (left + right + 1) >> 1; if(nums[mid] > target) right = mid - 1; else left = mid; } return nums[left] == target ? left : - 1; }}