二分查找

1、参考资料

https://leetcode-cn.com/problems/binary-search/

2、题目要求

题目描述

给定一个 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]之间。

3、代码思路

二分查找的前提是数组是排好序的数组，二分查找也是双指针的典型应用，我们定义两个指针 left 和 right，初始化时让 left 指向数组第一个元素，让 right 指向数组最后一个元素我们每次取 [left, right] 区间中间的元素，即 int middle = left + (right - left) / 2;，让 nums[middle] 比较如果 nums[middle] > target，则说明 target 在 [left, right] 的左半区间，所以应该让 right = middle - 1;如果 nums[middle] < target，则说明 target 在 [left, right] 的右半区间，所以应该让 left = middle + 1;如果 nums[middle] = target，则说明找到目标元素，返回目标值的索引(middle)即可如果遍历完整个数组(left > right)，都没有找到目标值，则说明数组中不存在此元素，返回 -1

4、代码实现

代码

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