[leetcode]704-二分查找

来源：力扣 （LeetCode）

链接：https://leetcode-cn.com/problems/binary-search

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一、题目描述

给定一个 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. 你可以假设 nums 中的所有元素是不重复的。
2. n 将在 [1, 10000]之间。
3. nums 的每个元素都将在 [-9999, 9999]之间。

二、二分查找

二分查找的前提要求是数组有序，一趟二分查找的算法描述为：

1. 确定数组上下边界，然后取中间值 mid 。
2. 对比中间值 mid 和目标值 target，此时有两种情况：
   • 如果 target 小于 mid，说明目标值在下边界区，继续在下半边界执行步骤 1 。
   • 如果 target 大于 mid，说明目标值在上边界区，继续在上半边界执行步骤 1 。
3. 如果上下边界一直找完都没有找到目标值，说明数组中不存在指定数据。

图文描述

在数组 [2, 3, 4, 5, 6, 7, 8] 中查找 3 。第一步，计算 mid 是下标为 3 的值 5，此时 5 比目标值 3 要大，说明 3 出现在 5 左边，要在 [low, mid) 进行下一步查找：

第二步，重新定位修改区域，查找的下标范围是 [0, 2] 。此时 mid 计算出来等于 1，下标等于 1 的元素值为 3，刚好就是我们要找的目标值，查找完成：

三、代码

需要注意的点已经在代码中标出：

1. 注意有符号、无符号以及数据是否会溢出。当前题目中数据不大，所以直接使用 int 。
2. 循环结束的条件是 low > high，所以循环条件一定是 low <= high，不要少了等于符号。
3. 没有找到目标值的时候，返回-1 。

这么简单的一个题目，提交了 4 次才通过。。。。基础很重要！！！