面试官：聊一下二分法

╰半夏微凉° 2023-10-06 11:14 21阅读 0赞

![format_png][]

### 来源：cnblogs.com/luoxn28/p/5767571.html ###

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

### **1、二分查找**    ###

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

![format_png 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`， 防止出现死循环， 程序也就能够正确的运行。

> 注意：代码中的判断条件必须是`while (left <= right)`，否则的话判断条件不完整，比如：`array[3] = {1, 3, 5};`待查找的键为5，此时在(`low < high`)条件下就会找不到，因为low和high相等时，指向元素5，但是此时条件不成立，没有进入`while()`中。

### **2、二分查找的变种** ###

关于二分查找，如果条件稍微变换一下，比如：数组之中的数据可能可以重复，要求返回匹配的数据的最小（或最大）的下标；更近一步， 需要找出数组中第一个大于`key`的元素（也就是最小的大于`key`的元素的）下标，等等。这些，虽然只有一点点的变化，实现的时候确实要更加的细心。

二分查找的变种和二分查找原理一样，主要就是变换判断条件（也就是边界条件），如果想直接看如何记忆这些变种的窍门，请直接翻到本文最后。下面来看几种二分查找变种的代码：

#### **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;
            }
        }
        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;
            }
        }
        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`的最左边元素下标。

// 查找第一个等于或者大于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;
        }
    }
    return xxx;

二分查找变种较多，不过它们的“套路”是一样的，以上代码就是其套路，如何快速写出二分查找的代码，只需按照以下步骤即可：

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

因为我们知道最后跳出`while (left <= right)`循环条件是`right < left`，且`right = left - 1`。最后`right`和`left`一定是卡在"边界值"的左右两边，如果是比较值为`key`，查找小于等于（或者是小于）`key`的元素，则边界值就是等于`key`的所有元素的最左边那个，其实应该返回`left`。

以数组`{1, 2, 3, 3, 4, 5}`为例，如果需要查找第一个等于或者小于3的元素下标，我们比较的key值是3，则最后`left`和`right`需要满足以下条件：

![format_png 2][]

我们比较的`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;
    }

【End】

查看更多面试题内容，请访问《**Java最常见200+面试题全解析**》，它包含的模块有：

*  Java、JVM 最常见面试题解析
 *  Spring、Spring MVC、MyBatis、Hibernate 面试题解析
 *  MySQL、Redis 面试题解析
 *  RabbitMQ、Kafka、Zookeeper 面试解析
 *  微服务 Spring Boot、Spring Cloud 面试解析

扫描下面二维码付费阅读

![format_png 3][]

关注下方二维码，订阅更多精彩内容。

![format_png 4][]

转发朋友圈，是对我最大的支持。

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9Icld3Nlp1WENzZ1lpYlVqQVM3ZTNlYldkaWFnWmJwaWEwWGRsUnpiNmtKbDFjNndOSWo3eTJpY0xXVVdPS21IY0JrRWliSk1aWDhndjRpYXk5T05SUEVVaDNvQS82NDA?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9RQ3U4NDlZVGFJT0NuOHBMTThKQmlhZEl5VmhnYlVucG5CRHRRTk1hdW9pYXFodWxvZFllV2FFM0dJR3JQZ3Q5dFl2Sm8zaWJQNlBDS0NkRjJpYld2VmpiYkEvNjQw?x-oss-process=image/format,png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9RQ3U4NDlZVGFJT0NuOHBMTThKQmlhZEl5VmhnYlVucG5XaWN1RmRXTVBSTkpvVlR0cmdObnI2TWplNEE4RmZkZ3pHbjhzSUc5R1RUZTk3U0RkZVpaZjBBLzY0MA?x-oss-process=image/format,png
[format_png 3]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9zWnlBSnRpYWVzV2NWd1pubUczb3V1V3N6aWFRaDVmeFNabUJkaWFpY3lmQWNRbVJ0WUtpY3BoZlZma1FDVDVsMFlZZ245WHdvcUdSaHpqNXN1QzVad2dsUGV3LzY0MA?x-oss-process=image/format,png
[format_png 4]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9Icld3Nlp1WENzaGhLaWNnd2hFQjR4bmZKemtWM1hYOENaMUlIRUI2VkZ6cmFIejdXWGcxY0FMQlJaYnBWOGxpYlNNVjRKcDJncXF5cW9rbFJGcEpWQUF3LzY0MA?x-oss-process=image/format,png