【数组】力扣704二分查找

2024-01-10 06:03:34

题目

力扣704:二分查找

思路

首先当看到有序的,升序的,没有重复的元素,那么就要想到使用二分查找方法。
其次要确认的就是把握边界问题,二分查找中,边界的控制十分重要。我们要确认是左闭右闭 [],还是左闭右开 [)。在二分查找的过程中,要保持不变量,就是在while寻找中每一次边界的处理都要坚持根据区间的定义来操作,这就是循环不变量规则

代码实现

版本一:左闭右闭 []

public int search(int[] arr, int target) {
    int left = 0;
    ing right = arr.length - 1;
    // 这里我们要想是left<right,还是<=呢?
    // 我们确认的区间是左闭右闭,那么当left = right的时候,也是在这个区间里,也是合法的,所以是<=
    while(left <= right) {
        // 计算出中间索引middle
        int middle = (left + right) / 2;
        // 如果中间索引上的这个元素大于目标值,说明target存在于左区间,要移动right索引
        if(arr[middle] > target) {
            // 为什么是middle-1呢?我们想arr[middle]已经大于了target,那么middle位置这个元素就不用再算了,
            // 直接比较middle的下一个位置就可以了,所以把right变为middle - 1即可
            right = middle - 1;
        } else if(arr[middle] < target) { // 说明target处于右区间,移动left索引
            // 参考上面解释
            left = middle + 1;
        } else {
            return middle;
        }
    }
    // 走到这里说明没找到符合的元素,返回-1
    return -1;
}

版本二:左闭右开 [)

public static int search(int[] arr, int target) {
    // 左闭右闭 [ ]
    int left = 0;
    int right = arr.length - 1;
    // 因为采用的是左闭右开,所以当left = right的时候 是没有意义的
    while (left < right) {
        // 计算middle中间值索引
        int middle = (left + right) / 2;
        // 中间值大于目标值,说明target处于左区间,移动right
        if (arr[middle] > target) {
            // 注意左闭右开[)
            right = middle;
        } else if (arr[middle] < target) {
            // 注意左闭右开[)
            left = middle + 1;
        } else {
            return middle;
        }
    }
    return -1;
}

推荐刷题

刷完二分查找,掌握其思想,推荐刷下面题目练手,进一步掌握。
保持一天两道即可
力扣35:搜索插入位置
力扣34:在排序数组中查找元素的第一个和最后一个位置

参考

代码随想录B站视频
代码随想录刷题路线

文章来源:https://blog.csdn.net/weixin_44078354/article/details/135410249
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。