# 兔子洞

**Published by:** [baba](https://paragraph.com/@baba-2/)
**Published on:** 2022-06-16
**URL:** https://paragraph.com/@baba-2/dHn6kcjgAPx1UcKJZCAK

## Content

二分查找 题目示例： 输入: nums = [-1,0,3,5,9,12], target = 9 输出: 4 解释: 9 出现在 nums 中并且下标为 4 注意：数组是有序的！！！！ 思路： 第一种方法： 我们定义 target 是在一个在左闭右闭的区间里，也就是[left, right] （这个很重要非常重要）。 区间的定义这就决定了二分法的代码应该如何写，因为定义target在[left, right]区间，所以有如下两点： while (left <= right) 要使用 <= ，因为left == right是有意义的，所以使用 <= if (nums[middle] > target) right 要赋值为 middle - 1，因为当前这个nums[middle]一定不是target，那么接下来要查找的左区间结束下标位置就是 middle - 1 左闭右闭区间 class Solution { public int search(int[] nums, int target) { // 避免当 target 小于nums[0] nums[nums.length - 1]时多次循环运算 if (target &#x3C; nums[0] || target > nums[nums.length - 1]) { return -1; } int left = 0, right = nums.length - 1; while (left &#x3C;= right) { int mid = left + ((right - left) >> 1); if (nums[mid] == target) return mid; else if (nums[mid] &#x3C; target) left = mid + 1; else if (nums[mid] > target) right = mid - 1; } return -1; } } 第二种方法： 定义 target 是在一个在左闭右开的区间里，也就是[left, right) while (left < right)，这里使用 < ,因为left == right在区间[left, right)是没有意义的 if (nums[middle] > target) right 更新为 middle，因为当前nums[middle]不等于target，去左区间继续寻找，而寻找区间是左闭右开区间，所以right更新为middle，即：下一个查询区间不会去比较nums[middle] class Solution { public int search(int[] nums, int target) { int left = 0, right = nums.length; while (left &#x3C; right) { int mid = left + ((right - left) >> 1); if (nums[mid] == target) return mid; else if (nums[mid] &#x3C; target) left = mid + 1; else if (nums[mid] > target) right = mid; } return -1; } }

## Publication Information

- [baba](https://paragraph.com/@baba-2/): Publication homepage
- [All Posts](https://paragraph.com/@baba-2/): More posts from this publication
- [RSS Feed](https://api.paragraph.com/blogs/rss/@baba-2): Subscribe to updates