704 二分查找

704. 二分查找

力扣题目链接

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

思路

对于在有序无重复数组中查找目标值的问题，可以考虑二分查找来实现。

题目中说到，nums 中的所有元素是不重复的，且 nums 按升序排列，所以可以考虑使用二分查找法。

二分查找的逻辑比较简单，但在边界条件的处理上很容易出错。例如，我们写 while(left < right) 和 while(left <= right) 对应的处理方式就完全不同。

举一个简单的例子，假设数组中只有一个元素 5，目标值 target也等于 5。如果使用 while(left < right) 的写法，那么 right 就应该初始化为 1，left 初始化为 0。而如果使用 while(left <= right) 写法，left 和 right 都应初始化为 0。所以两种写法的不同就在于边界条件的处理。

所以根据边界条件的处理方式，二分查找有以下两种写法。

第一种写法

假设数组元素是 [1,2,3,4,5,6,7]，target = 3，我们使用 while(left < right) 写法实现二分排序。

这种写法里，left = 0,right = 7，运算过程如图所示

代码的关键在于，当 nums[mid] < nums[right] 时，right = mid。循环中 right是开区间，这里也应是开区间，保持一致。

对应的代码如下:（Kotlin）

class Solution {
    fun search(nums: IntArray, target: Int): Int {
        var left = 0
        var right = nums.size // [left,right) 右侧为开区间，right 设置为 nums.size
        while (left < right) {
            val mid = (left + right) / 2
            if (nums[mid] < target) left = mid + 1
            else if (nums[mid] > target) right = mid // 代码的核心，循环中 right 是开区间，这里也应是开区间
            else return mid
        }
        return -1 // 没有找到 target ，返回 -1
    }
}

第二种写法

假设数组元素是 [1,2,3,4,5,6,7]，target = 3，我们使用 while(left <= right) 写法实现二分排序。

这种写法里，`left = 0,right = 76，运算过程如图所示

代码的关键在于，当 nums[mid] < nums[right] 时，right = mid - 1。循环中 right是闭区间，这里也应是闭区间，保持一致。

对应的代码如下:（Kotlin）

class Solution {
    
    fun search(nums: IntArray, target: Int): Int {
    
        var left = 0
        var right = nums.size - 1 // [left,right] 右侧为闭区间，right 设置为 nums.size - 1
        while (left <= right) {
    
            val mid = (left + right) / 2
            if (nums[mid] < target) left = mid + 1
            else if (nums[mid] > target) right = mid - 1 // 代码的核心，循环中 right 是闭区间，这里也应是闭区间
            else return mid
        }
        return -1 // 没有找到 target ，返回 -1
    }
}