从小白开始刷算法 二分法篇 leetcode.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

题目来源：力扣（LeetCode）

二分法

能否写出：能写出。

时间：20多分钟

思路：

初始化 start 为数组的起始索引（0）, end 为数组的末尾索引（nums.length-1）。

1. 进入循环，只要 start 不大于 end，就进行循环操作。
   
2. 在每次循环中，计算中间元素的索引 middle，通过将 start 和 end 的平均值赋给 middle。这样可以确保我们每次都在数组的中间位置进行查找。
   
3. 检查中间元素 nums[middle] 是否等于目标值 target，如果是，则找到了目标值，返回 middle。
   
4. 如果中间元素 nums[middle] 大于目标值 target，说明目标值可能在中间元素的左侧，将 end 更新为 middle-1，缩小查找范围到左半部分。
   
5. 如果中间元素 nums[middle] 小于目标值 target，说明目标值可能在中间元素的右侧，将 start 更新为 middle+1，缩小查找范围到右半部分。
   
6. 继续下一次循环，直到 start 大于 end，此时查找范围为空，循环结束。
   
7. 如果循环结束仍未找到目标值，则返回 -1，表示目标值不存在于数组中。
   

在代码中，start + (end - start) / 2 的目的是为了计算中间元素的索引 middle。这样的计算方式是为了避免整数溢出的问题，并确保得到正确的中间索引值。

start + (end - start) / 2 等价于 (start + end) / 2，它们都可以用来计算中间索引。然而，使用 (start + end) / 2 的方式可能会导致整数溢出的问题，特别是当 start 和 end 很大时。通过使用 (end - start) / 2 可以避免这个问题，因为这样计算的差值一定是非负的。

例如，假设 start = 10000，end = 20000，使用 (start + end) / 2 的方式计算中间索引会得到 15000，这是正确的。但是，如果 start 和 end 很大，例如 start = 2^31 - 1，end = 2^31 - 1，计算中间索引时使用 (start + end) / 2 就会导致整数溢出，得到错误的结果。

因此，使用 (end - start) / 2 可以确保计算中间索引时避免整数溢。

b站 up 爱学习的饲养员 陈述了这个问题，我这边举了个例子扩展。

// 仅是我的思路代码，leetcode上大神更厉害
class Solution {
    public int search(int[] nums, int target) {
        int end = nums.length-1;
        int start = 0;
        while (start<=end){
          //计算中间元素的索引
            int middle= start+(end-start)/2;
            //找到目标值，返回
            if(nums[middle]==target){
                return middle;
            }
            //目标值可能在中间元素的左侧
            if(nums[middle]>target){
            //将 end 更新为 middle-1，缩小查找范围到左半部分
                end = middle-1;
            }else {
            //目标值可能在中间元素的右侧
                start = middle+1;
            }
        }
        return -1;
    }
}

时间复杂度： O(log n)

空间复杂度：O(1)