你真的会写二分查找吗？

逃离我推掉我的手 2021-07-31 16:46 462阅读 0赞

点击上方 **蓝色字体** ，选择“标星公众号”

优质文章，第一时间送达

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg]

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

**1、二分查找**

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

![640?wx\_fmt=png][640_wx_fmt_png]

/**	
     * 二分查找，找到该值在数组中的下标，否则为-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` 需要满足以下条件：

![640?wx\_fmt=png][640_wx_fmt_png 1]

我们比较的 `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.htmlhttp://www.cnblogs.com/luoxn28/category/802645.html

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

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

**推** **荐** **阅** **读**

***1.***

***2.  ***

***3.  ***

***4. ****** ***

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 1]

**喜欢文章，点个** **在看** ** ** ![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 2]

[640_wx_fmt_jpeg]: /images/20210731/8e938e28504d4cda970b4dc75534ff80.png?wx_fmt=jpeg
[640_wx_fmt_png]: /images/20210731/6f2cc46abc96456f87645120de1e5f3e.png?wx_fmt=png
[640_wx_fmt_png 1]: /images/20210731/d2e9222eaa4f4128b6fd5bdc9991b50d.png?wx_fmt=png
[640_wx_fmt_jpeg 1]: /images/20210731/c2c0683729e2436d8a05525fc6f1f4cf.png?wx_fmt=jpeg
[640_wx_fmt_jpeg 2]: /images/20210731/b424a335a649478e88bff6ac6ea98c99.png?wx_fmt=jpeg