阅读全文

⭐⭐⭐ Spring Boot 项目实战	⭐⭐⭐ Spring Cloud 项目实战
《Dubbo 实现原理与源码解析 —— 精品合集》	《Netty 实现原理与源码解析 —— 精品合集》
《Spring 实现原理与源码解析 —— 精品合集》	《MyBatis 实现原理与源码解析 —— 精品合集》
《Spring MVC 实现原理与源码解析 —— 精品合集》	《数据库实体设计合集》
《Spring Boot 实现原理与源码解析 —— 精品合集》	《Java 面试题 + Java 学习指南》

摘要: 原创出处 http://blog.chinaunix.net/uid-1844931-id-3337784.html 「liubird」欢迎转载，保留摘要，谢谢！

• 1. 找出第一个与key相等的元素
• 2. 找出最后一个与key相等的元素
• 3. 查找第一个等于或者大于Key的元素
• 4. 查找第一个大于key的元素
• 5. 查找最后一个等于或者小于key的元素
• 6. 查找最后一个小于key的元素

---

🙂🙂🙂关注**微信公众号：【芋道源码】**有福利：

1. RocketMQ / MyCAT / Sharding-JDBC 所有源码分析文章列表
2. RocketMQ / MyCAT / Sharding-JDBC 中文注释源码 GitHub 地址
3. 您对于源码的疑问每条留言都将得到认真回复。甚至不知道如何读源码也可以请教噢。
4. 新的源码解析文章实时收到通知。每周更新一篇左右。
5. 认真的源码交流微信群。

---

前几天在论坛上看到有统计说有80%的程序员不能够写对简单的二分法。二分法不是很简单的吗？ 这难道不是耸人听闻？

其实，二分法真的不那么简单，尤其是二分法的各个变种。 最最简单的二分法，就是从一个排好序的数组之查找一个key值。 如下面的程序：

1. int search(int *arr, int n, int key)
2. {
3. ​    int left = 0, right = n-1;
4. ​    while(left<=right) {
5. ​        int mid = left + ((right - left) << 1);
6. ​        if (arr[mid] == key) return mid;
7. ​        else if(arr[mid] > key) right = mid - 1;
8. ​        else left = mid + 1;
9. ​    }
10. ​    return -1;
11. }

这个程序，相信只要是一个合格的程序员应该都会写。 稍微注意一点， 每次移动left和right指针的时候，需要在mid的基础上+1或者-1， 防止出现死循环， 程序也就能够正确的运行。

但如果条件稍微变化一下， 你还会写吗？如，数组之中的数据可能可以重复，要求返回匹配的数据的最小（或最大）的下标；更近一步， 需要找出数组中第一个大于key的元素（也就是最小的大于key的元素的）下标，等等。 这些，虽然只有一点点的变化，实现的时候确实要更加的细心。 下面列出了这些二分检索变种的实现。

1. 找出第一个与key相等的元素

1. int searchFirstEqual(int *arr, int n, int key)
2. {
3. ​    int left = 0, right = n-1;
4. ​    while(left<=right) {
5. ​        int mid = (left+right)/2;
6. ​        if(arr[mid] >= key) right = mid - 1;
7. ​        else if(arr[mid] < key) left = mid + 1;
8. ​    }
9. ​    if( left < n && arr[left] == key) return left;
10. ​    return -1;
11. }

2. 找出最后一个与key相等的元素

1. int searchLastEqual(int *arr, int n, int key)
2. {
3. ​    int left = 0, right = n-1;
4. ​    while(left<=right) {
5. ​        int mid = (left+right)/2;
6. ​        if(arr[mid] > key) right = mid - 1;
7. ​        else if(arr[mid] <= key) left = mid + 1;
8. ​    }
9. ​    if( right>=0 && arr[right] == key) return right;
10. ​    return -1;
11. }

3. 查找第一个等于或者大于Key的元素

1. int searchFirstEqualOrLarger(int *arr, int n, int key)
2. {
3. ​    int left=0, right=n-1;
4. ​    while(left<=right) {
5. ​        int mid = (left+right)/2;
6. ​        if(arr[mid] >= key) right = mid-1;
7. ​        else if (arr[mid] < key) left = mid+1;
8. ​    }
9. ​    return left;
10. }

4. 查找第一个大于key的元素

1. int searchFirstLarger(int *arr, int n, int key)
2. {
3. ​    int left=0, right=n-1;
4. ​    while(left<=right) {
5. ​        int mid = (left+right)/2;
6. ​        if(arr[mid] > key) right = mid-1;
7. ​        else if (arr[mid] <= key) left = mid+1;
8. ​    }
9. ​    return left;
10. }

5. 查找最后一个等于或者小于key的元素

1. int searchLastEqualOrSmaller(int *arr, int n, int key)
2. {
3. ​    int left=0, right=n-1;
4. ​    while(left<=right) {
5. ​        int m = (left+right)/2;
6. ​        if(arr[m] > key) right = m-1;
7. ​        else if (arr[m] <= key) left = m+1;
8. ​    }
9. ​    return right;
10. }

6. 查找最后一个小于key的元素

1. int searchLastSmaller(int *arr, int n, int key)
2. {
3. ​    int left=0, right=n-1;
4. ​    while(left<=right) {
5. ​        int mid = (left+right)/2;
6. ​        if(arr[mid] >= key) right = mid-1;
7. ​        else if (arr[mid] < key) left = mid+1;
8. ​    }
9. ​    return right;
10. }

下面是一个测试的例子：

1. int main(void)
2. {
3. ​    int arr[17] = {1,
4. ​                   2, 2, 5, 5, 5,
5. ​                   5, 5, 5, 5, 5,
6. ​                   5, 5, 6, 6, 7};
7. ​    printf("First Equal           : %2d \n", searchFirstEqual(arr, 16, 5));
8. ​    printf("Last Equal            : %2d \n", searchLastEqual(arr, 16, 5));
9. ​    printf("First Equal or Larger : %2d \n", searchFirstEqualOrLarger(arr, 16, 5));
10. ​    printf("First Larger          : %2d \n", searchFirstLarger(arr, 16, 5));
11. ​    printf("Last Equal or Smaller : %2d \n", searchLastEqualOrSmaller(arr, 16, 5));
12. ​    printf("Last Smaller          : %2d \n", searchLastSmaller(arr, 16, 5));
13. ​    system("pause");
14. ​    return 0;
15. }

最后输出结果是：

1. First Equal           :  3
2. Last Equal            : 12
3. First Equal or Larger :  3
4. First Larger          : 13
5. Last Equal or Smaller : 12
6. Last Smaller          :  2

很多的时候，应用二分检索的地方都不是直接的查找和key相等的元素，而是使用上面提到的二分检索的各个变种，熟练掌握了这些变种，当你再次使用二分检索的检索的时候就会感觉的更加的得心应手了。