胖虎的工具箱-编程导航 胖虎的工具箱-编程导航

你真的会写二分查找吗？

2年前 (2022) 程序员胖胖胖虎阿
295 0 0
点击上方
蓝色字体
，选择“标星公众号”
优质文章，第一时间送达
你真的会写二分查找吗？

来源 | cnblogs.com/luoxn28/p/5767571.html


1、二分查找

二分查找是一个基础的算法，也是面试中常考的一个知识点。二分查找就是将查找的键和子数组的中间键作比较，如果被查找的键小于中间键，就在左子数组继续查找；如果大于中间键，就在右子数组中查找，否则中间键就是要找的元素。

你真的会写二分查找吗？

/** * 二分查找，找到该值在数组中的下标，否则为-1 */static int binarySerach(int[] array, int key) {    int left = 0;    int right = array.length - 1;
    // 这里必须是 <=    while (left <= right) {        int mid = (left + right) / 2;        if (array[mid] == key) {            return mid;        }        else if (array[mid] < key) {            left = mid + 1;        }        else {            right = mid - 1;        }    }
    return -1;}
每次移动
left
和
right
指针的时候，需要在mid的基础上
+1
或者
-1
， 防止出现死循环， 程序也就能够正确的运行。欢迎微信搜索 Web项目聚集地 获取更多博文。
注意：代码中的判断条件必须是
while (left <= right)
，否则的话判断条件不完整，比如：
array[3] = {1, 3, 5};
待查找的键为5，此时在(
low < high
)条件下就会找不到，因为low和high相等时，指向元素5，但是此时条件不成立，没有进入
while()
中。

2、二分查找的变种

关于二分查找，如果条件稍微变换一下，比如：数组之中的数据可能可以重复，要求返回匹配的数据的最小（或最大）的下标；更近一步， 需要找出数组中第一个大于
key
的元素（也就是最小的大于
key
的元素的）下标，等等。这些，虽然只有一点点的变化，实现的时候确实要更加的细心。欢迎微信搜索 Web项目聚集地 获取更多博文。
二分查找的变种和二分查找原理一样，主要就是变换判断条件（也就是边界条件），如果想直接看如何记忆这些变种的窍门，请直接翻到本文最后。下面来看几种二分查找变种的代码：

2.1、查找第一个与key相等的元素

查找第一个相等的元素，也就是说等于查找
key
值的元素有好多个，返回这些元素最左边的元素下标。
// 查找第一个相等的元素static int findFirstEqual(int[] array, int key) {    int left = 0;    int right = array.length - 1;
    // 这里必须是 <=    while (left <= right) {        int mid = (left + right) / 2;        if (array[mid] >= key) {            right = mid - 1;        }        else {            left = mid + 1; // 欢迎微信搜索 Web项目聚集地 获取更多博文。        }    }    if (left < array.length && array[left] == key) {        return left;    }
    return -1;}

2.2、查找最后一个与key相等的元素

查找最后一个相等的元素，也就是说等于查找
key
值的元素有好多个，返回这些元素最右边的元素下标。
// 查找最后一个相等的元素static int findLastEqual(int[] array, int key) {    int left = 0;    int right = array.length - 1;
    // 这里必须是 <=    while (left <= right) {        int mid = (left + right) / 2;        if (array[mid] <= key) {            left = mid + 1;        }        else {            right = mid - 1; //欢迎微信搜索 Web项目聚集地 获取更多博文。        }    }    if (right >= 0 && array[right] == key) {        return right;    }
    return -1;}

2.3、查找最后一个等于或者小于key的元素

查找最后一个等于或者小于
key
的元素，也就是说等于查找
key
值的元素有好多个，返回这些元素最右边的元素下标；如果没有等于
key
值的元素，则返回小于
key
的最右边元素下标。
// 查找最后一个等于或者小于key的元素static int findLastEqualSmaller(int[] array, int key) {    int left = 0;    int right = array.length - 1;
    // 这里必须是 <=    while (left <= right) {        int mid = (left + right) / 2;        if (array[mid] > key) {            right = mid - 1;        }        else {            left = mid + 1;        }    }    return right;}

2.4、查找最后一个小于key的元素

查找最后一个小于key的元素，也就是说返回小于key的最右边元素下标。

// 查找最后一个小于key的元素static int findLastSmaller(int[] array, int key) {    int left = 0;    int right = array.length - 1;
    // 这里必须是 <=    while (left <= right) {        int mid = (left + right) / 2;        if (array[mid] >= key) {            right = mid - 1;        }        else {            left = mid + 1;        }    }    return right;}

2.5、查找第一个等于或者大于key的元素

查找第一个等于或者大于
key
的元素，也就是说等于查找
key
值的元素有好多个，返回这些元素最左边的元素下标；如果没有等于
key
值的元素，则返回大于
key
的最左边元素下标。欢迎微信搜索 Web项目聚集地 获取更多博文。
// 查找第一个等于或者大于key的元素static int findFirstEqualLarger(int[] array, int key) {    int left = 0;    int right = array.length - 1;
    // 这里必须是 <=    while (left <= right) {        int mid = (left + right) / 2;        if (array[mid] >= key) {            right = mid - 1;        }        else {            left = mid + 1;        }    }    return left;}
2.6、查找第一个大于key的元素




查找第一个等于key的元素，也就是说返回大于key的最左边元素下标。

// 查找第一个大于key的元素static int findFirstLarger(int[] array, int key) {    int left = 0;    int right = array.length - 1;
    // 这里必须是 <=    while (left <= right) {        int mid = (left + right) / 2;        if (array[mid] > key) {            right = mid - 1;        }        else {            left = mid + 1;        }    }    return left;}

3、二分查找变种总结

// 这里必须是 <=while (left <= right) {    int mid = (left + right) / 2;    if (array[mid] ? key) {        //... right = mid - 1;    }    else {        // ... left = mid + 1; 欢迎微信搜索 Web项目聚集地 获取更多博文。    }}return xxx;
二分查找变种较多，不过它们的“套路”是一样的，以上代码就是其套路，如何快速写出二分查找的代码，只需按照以下步骤即可：

1、首先判断出是返回left，还是返回right

因为我们知道最后跳出
while (left <= right)
循环条件是
right < left
，且
right = left - 1
。
最后
right
和
left
一定是卡在"边界值"的左右两边，如果是比较值为
key
，查找小于等于（或者是小于）
key
的元素，则边界值就是等于
key
的所有元素的最左边那个，其实应该返回
left
。欢迎微信搜索 Web项目聚集地 获取更多博文。
以数组
{1, 2, 3, 3, 4, 5}
为例，如果需要查找第一个等于或者小于3的元素下标，我们比较的key值是3，则最后
left
和
right
需要满足以下条件：

你真的会写二分查找吗？

我们比较的
key
值是3，所以此时我们需要返回
left
。

2、判断出比较符号

int mid = (left + right) / 2;if (array[mid] ? key) {    //... right = xxx;}else {    // ... left = xxx;}

也就是这里的if (array[mid] ? key) 中的判断符号，结合步骤1和给出的条件，如果是查找小于等于key的元素，则知道应该使用判断符号>=，因为是要返回left，所以如果array[mid]等于或者大于key，就应该使用>=，以下是完整代码

// 查找小于等于key的元素int mid = (left + right) / 2;if (array[mid] >= key) {    right = mid - 1;}else {    left = mid + 1;}

参考：

http://blog.chinaunix.net/uid-1844931-id-3337784.html
http://www.cnblogs.com/luoxn28/category/802645.html

如果喜欢本篇文章，欢迎转发、点赞。关注订阅号「Web项目聚集地」，回复「进群」即可进入无广告技术交流。

推
荐
阅
读

1.  Java 实现 QQ 登陆

2.  请给 Spring Boot 多一些内存

3.  如何从零搭建百亿流量系统 ？

4.  惊了！原来 Web 发展历史是这样的

你真的会写二分查找吗？
喜欢文章，点个
在看
 
你真的会写二分查找吗？

本文分享自微信公众号 - Java后端（web_resource）。
如有侵权，请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”，欢迎正在阅读的你也加入，一起分享。

版权声明：程序员胖胖胖虎阿 发表于 2022年9月18日 下午3:56。
转载请注明：你真的会写二分查找吗？ | 胖虎的工具箱-编程导航

相关文章

Java 模拟数据库连接池的实现
程序员胖胖胖虎阿
202
IDEA2019注册码(IntelliJ IDEA正版永久激活码每日更新)
程序员胖胖胖虎阿
55
12 个免费又酷炫的 IntelliJ IDEA 插件
程序员胖胖胖虎阿
260
IntelliJ IDEA2019破解码(IDEA最新永久激活破解教程,激活破解教程)
程序员胖胖胖虎阿
198
IntelliJ IDEA安装及激活工具(IDEA2019激活码激活教程,最新有效IDEA激活码)
程序员胖胖胖虎阿
66
Java 处理 Exception 的 9 个最佳实践
程序员胖胖胖虎阿
153

暂无评论

暂无评论...
致力于称为最好的程序员导航网站

友链申请 免责声明 关于我们

Copyright © 2022  胖虎的工具箱-编程导航   陇ICP备2022001249号