二分查找的简单实现

小灰灰 2024-03-24 10:56 14阅读 0赞

> 简单记录了一下二分查找的实现

#### 文章目录 ####

前言

一、二分查找是什么？

二、代码实现

总结

--------------------

## 前言 ##

这天，六花来到一家公司面试，面试官说：“给你一段**有序整型数组**和一个值，你就写一道简单的查询返回下标吧。”你一听，嘴都笑裂到后脑勺了。拿出键盘就敲下了一段for循环遍历查询。面试官一看，直接不停点头并语重心长的对你说：“小伙子，我看你骨骼..水平不错！回去等消息吧，我看你机会很大的！”你听了后，便激动的回到家等待消息心想“区区面试，不过如此。。。”从此，再也没有了下文。

## 一、二分查找是什么？ ##

给一个值，对一段**有序整型数组**进行查询，如\[1, 2, 3, 4, 5, 6, 7, 8\]，需要查找 5 对应的位置（下标）。选择数组**中间的数字（这里是4）**和需要查找的目标值比较，如果相等就直接返回答案（下标）。如果不相等，就要考虑两种情况：

1）如果中间的数字**大于**目标值，则**中间数字向右**的**所有数字都大于目标值**，全部排除

2）如果中间的数字**小于**目标值，则**中间数字向左**的**所有数字都小于目标值**，全部排除

然后就这样循环下去。

**注意：**这里多次强调了 是有序整型数组，毕竟如果不有序就无法确定中间数字另一边的数能完全大于（小于）目标数字然后排除了。其次，查询的目标值只能是一个，不能是多个。

## 二、代码实现 ##

二分查找开闭不一样，对应的迭代方式也不一样，有以下两种方式：

*  左闭右闭`[left, right]`
 *  左闭右开\[left, right)

**左闭右闭代码如下：**

private static int binarySearch(int target, int[] arry) {
            int left = 0, right = arry.length - 1;
            while (left <= right){
                int mid = (left + right) >>> 1;
                if (arry[mid] == target){
                    return mid;
                } else if (arry[mid] < target) {
                    left = mid + 1;
                } else if (arry[mid] > target) {
                    right = mid - 1;
                }
            }
            return -1;
        }

**左闭右开**的区别在于 数组右边界选择的就是数组长度，而 左闭右闭的有边界选择的数组长度-1。还有循环条件时的判断。详情请看：[【二分查找】详细图解\_Charon\_cc的博客-CSDN博客][Charon_cc_-CSDN]

**代码如下：**

private static int binarySearch(int target, int arry[])
        {
            int left = 0;
            int right = arry.length; //定义target在左闭右开的区间里，即[left, right)
            while (left < right) {	//因为left = right的时候，在[left, right)区间上无意义
                int middle = (left + right) >>> 1;
                if (arry[middle] > target) {
                    right = middle; //target 在左区间，在[left, middle)中 
                } else if (arry[middle] < target) {
                    left = middle + 1;
                } else {
                    return middle;
                }
            }
            // 没找到就返回-1
            return -1;
        }

**测试：**

> 给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例一：

> 输入: nums = \[-1,0,3,5,9,12\], target = 9  
> 输出: 4  
> 解释: 9 出现在 nums 中并且下标为 4

结果：

![279e88627d2944ec939bd765797dd6cc.png][]

示例二：

> 输入: nums = \[-1,0,3,5,9,12\], target = 2  
> 输出: -1  
> 解释: 2 不存在 nums 中因此返回 -1

结果：

![4022994c7cac4b2b8a81f3552ac5381b.png][]

--------------------

## 总结 ##

二分查找最重要的两个点，就是循环条件和后续的区间赋值问题。

两者是相互联系，相互影响的，所以就需要两者统一，如果两者不统一，就会出现问题

所以循环条件和赋值问题必须统一，也就是循环不变量。

[Charon_cc_-CSDN]: https://blog.csdn.net/qq_45978890/article/details/116094046?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522168007076816800186586965%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=168007076816800186586965&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_positive~default-1-116094046-null-null.142%5Ev77%5Econtrol_1,201%5Ev4%5Eadd_ask,239%5Ev2%5Einsert_chatgpt&utm_term=%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE&spm=1018.2226.3001.4187
[279e88627d2944ec939bd765797dd6cc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/9decf72678ec469d959c867e39887f18.png
[4022994c7cac4b2b8a81f3552ac5381b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/1afbeceda6ac48d3b96578883d993214.png