数据结构与算法之二分查找三模板

作者: 程序花生 | 来源:发表于2021-01-19 21:13 被阅读0次

二分查找是分治法的最基本的一种，其应用场景多为在有序数组内找寻到目标元素，将区间一分为二，与中值进行比较，如若与区间中值不等，则所查找目标元素仅需前往一分为二的相应的区间进行查找即可，重复上述步骤直至找到或者满足查找终止条件。
时间复杂度:O(logn)
空间复杂度:O(1)
本文框架主要来自LeetCode探索之二分查找，并记录自己的理解与学习过程。

二分查找模板１

模板（Java+Go版本）

public class BinarySearch {
    public static int binarySearch(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        int mid;
        while(left <= right) {
            mid = left + (right - left)/2;
            if(nums[mid] == target) return mid;
            if(nums[mid] > target) right = mid - 1;
            if(nums[mid] < target) left = mid + 1;
        }
        return -1;
    }
    public static void main(String[] args) {
        int[]nums = {1,2,3,4,5,6,7,8};
        System.out.print("array: ");
        for(int num : nums) {
            System.out.print(num+" ");
        }
        System.out.println();
        int number = 5;
        System.out.printf("BinarySearch %d in this array, index: %d\n",number, binarySearch(nums,number));
        number = 0;
        System.out.printf("BinarySearch %d in this array, index: %d\n",number, binarySearch(nums,number));
    }
}

package main

import "fmt"

func binarySearch(nums []int, target int) int {
    left, right := 0, len(nums)-1
    for left < right{
        mid := left + (right - left)/2
        if nums[mid] == target {
            return mid
        }else if nums[mid] > target {
            right = mid - 1
        }else{
            left = mid + 1
        }
    }
    return -1
}

func main(){
    nums := []int{1,2,3,4,5,8,9,10}
    fmt.Println("array:",nums)
    num := 8
    fmt.Printf("binary search %d in the array, index:%d\n", num, binarySearch(nums,num))
    num = 7
    fmt.Printf("binary search %d in the array, index:%d\n", num, binarySearch(nums,num))
}

模板分析

作为一款最基础大家耳熟能详的二分查找模板，模板1主要是用来从有序数组中查找某一元素是否存在，不存在则返回-1,存在则返回元素所在位置。

模板语法

起始条件: left = 0, right = length(nums) - 1
终止条件: left >= right (left > right)
继续查找左侧区间: right =mid - 1
继续查找右侧区间: left =mid + 1
返回值: found=>mid not found: -1

分析

为什么继续查找分别需要 +1 -1

从起始条件可以看出，每次二分查找的区间为[left, right]，即区间两边闭合可取。
因此在target与nums[mid]进行比较时，左侧区间和右侧区间分别改变为了[left, mid - 1]和[mid + 1, right]，以确保每次mid处的元素不会重复拿出来进行比较（防止死循环）。

循环终止条件为何是“left <= right”而非“left < right”

终止条件left <= right说明最后left < right，区间从最初的[0, length(nums)-1]变为了空[]，所有的可能的nums[mid]都参与了与target的匹配，并且匹配失败了，这意味着目标元素不在给定数组内，因此结尾直接返回-1以表示未查询到。
如果是left < right，最后left ＝ right，区间从最初的[0, length(nums)-1]变为了[left,left]，区间内还有一个元素没有与target进行匹配。

是否可以使用“left < right”

答案是可以的，只需要最后记得把剩下的最后一个元素与target进行比较即可。仅以Java为例修改如下

        ......
        while(left < right) {
            ......
        }
        return nums[left] == target? left : -1;

模板例题

LeetCode 33. 搜索旋转排序数组

具体问题

假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
你可以假设数组中不存在重复的元素。
你的算法时间复杂度必须是 O(log n) 级别。
示例 1:
输入: nums = [4,5,6,7,0,1,2], target = 0
输出: 4
示例 2:
输入: nums = [4,5,6,7,0,1,2], target = 3
输出: -1\

题目解析

这是一道典型使用模板1的题目，虽然不是完全有序但是该数组是分段有序的未发生旋转的部分与发生旋转的部分都是升序的，并且题目要求查找目标元素所在位置，因此二话不说，首先想到二分法。
那么接下来是如何二分的问题了，根据刚才所述，该数组是分段有序的，则mid的位置很微妙，要么nums[mid]是处于旋转数组中前半段未旋转部分，要么属于后半段被旋转的数组。那么接下来就需要进行二分操作了：

以上图为例，将nums[mid]与nums[right]相比较，发现nums[mid]>nums[right]，或者将nums[mid]与nums[left]相比较发现nums[mid]>nums[left]。这说明mid处在未发生旋转的数组部分，即[left, mid-1]是有序的数组段，那么可以先判断target在mid处，然后判断是否在[left, mid-1]内，如果在，则继续在[left, mid - 1]进行二分操作，否则说明target处在[mid + 1, right]内，重复上述二分操作即可。

解法(Java+Go版本)

class Solution {
    public int search(int[] nums, int target) {
        if(nums==null||nums.length==0)  return -1;
        int left = 0, right = nums.length-1, mid;
        while(left <= right) {
            mid = left + (right - left)/2;
            if(target == nums[mid]) return mid;
             if(nums[right] >= nums[mid]) { //[mid + 1, right]是有序的数组段
                if(target  <= nums[right] && target > nums[mid])
                    left = mid + 1;
                 else
                    right = mid - 1;
            }else{//[left, mid - 1]是有序的数组段
             if(target >= nums[left] && target < nums[mid])
                    right = mid - 1;
                else
                    left = mid + 1;
            }   
        }
        return -1;
    }
}

func search(nums []int, target int) int {
    left, right := 0, len(nums)-1
    for left <= right{
        mid := left + (right-left)/2
        if nums[mid] == target { 
            return mid
        }
        if nums[left] <= nums[mid] {//[left, mid - 1]是有序的数组段
            if target >= nums[left] && target < nums[mid] {
                right = mid - 1
            }else{
                left = mid + 1
            }
        }else{//[mid + 1, right]是有序的数组段
            if target <= nums[right] && target > nums[mid] {
                left = mid + 1
            }else{
                right = mid - 1
            }
        }
    }
    return -1
}

二分查找模板２

模板（Java+Go版本）

public class BinarySearch {
    public static int binarySearch(int[] nums, int target) {
        int left = 0, right = nums.length;
        int mid;
        while(left < right) {
            mid = left + (right - left)/2;
            if(nums[mid] == target) right = mid;
            if(nums[mid] > target) right = mid;
            if(nums[mid] < target) left = mid + 1;
        }
        return left;
    }

    public static void main(String[] args) {
        int[]nums = {1,2,3,4,5,6,7,7,8,8};
        System.out.print("array: ");
        for(int num : nums) {
            System.out.print(num+" ");
        }
        System.out.println();
        int number = 5;
        System.out.printf("BinarySearch %d in this array, index: %d\n",number, binarySearch2(nums,number));
        number = 7;
        System.out.printf("BinarySearch %d in this array, index: %d\n",number, binarySearch2(nums,number));
    }
}

```go

func binarySearch(nums []int, target int) int {
    left, right := 0, len(nums)
    for left < right{
        mid := left + (right - left)/2
        if nums[mid] == target {
            right = mid
        }else if nums[mid] > target {
            right = mid
        }else{
            left = mid + 1
        }
    }
    return left
}

func main() {
    nums := []int{1,2,3,4,5,8,9,10}
    fmt.Println("array:",nums)
    num := 8
    fmt.Printf("binary search %d in the array, index:%d\n",num,binarySearch(nums,num))
    num = -1
    fmt.Printf("binary search %d in the array, index:%d\n",num,binarySearch(nums,num))
}

模板分析

这一款的二分查找模板相当于是第一款的进阶版，模板２主要是用来从有序数组中查找某一元素是否存在，不存在则返回应当插入的位置,存在则返回元素所在位置，当升序数组中有多个与target相等元素出现时，也可以理解为查找数组中target数字的“产生的左边界”。

模板语法

起始条件: left = 0, right = length(nums)
终止条件: left < right (left = right) 继续查找左侧区间: right =mid
继续查找右侧区间: left =mid + 1
返回值: left\

分析

为什么继续查找分别left需要+1,而right不再-1

从起始条件可以看出，每次二分查找的区间为[left, right)，即区间左闭右开。
因此在target与nums[mid]进行比较时，左侧区间和右侧区间分别改变为了[left, mid)和[mid + 1, right)，同样是确保每次mid处的元素不会重复拿出来进行比较（防止死循环）。

循环终止条件为何变成了“left < right”

终止条件left < right说明最后left ＝ right，区间从最初的[0, length(nums))变为了空[left,left)，同样所有的可能的nums[mid]都参与了与target的比较，并且锁定了target在数组应当插入的位置（也就是大于数组中前多少个元素），因此如果数组中有与target相等的元素就会返回该元素，如果没有，就是告诉你：“你如果想把我放到这个数组中，那我的位置应该在这里”。
如果是left <＝ right，最后left ＝ right = mid，如果nums[mid]恰好大于target，那么对于上述循环来说可能就造成了死循环

是否可以使用“left < right”

理论上是可以的，但是意义不是很大，因为没有必要再在循环里判断三者是否相同。

是否可以返回-1表示未查询到

由上文所述，最终left,right相等返回的是target应当在的位置，所以比较nums[left]与target的值即可。仅以Java为例修改如下：

    ......
    return nums[left] == target? left : -1;
}

有的题目right是从length(nums)-1开始的，这是为啥

这种情况，是因为或许在循环体内有涉及到nums[right]或者right = length(nums)会导致数组溢出的情况下才将right赋值为right = length(nums)-1,可以参考下例
LeetCode 162. 寻找峰值
剑指 Offer 11. 旋转数组的最小数字(这个题目又有加深)

模板例题

LeetCode 278. 第一个错误的版本

具体问题

你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。
假设你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。
你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数>来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
示例:
给定 n = 5，并且 version = 4 是第一个错误的版本。
调用 isBadVersion(3) -> false
调用 isBadVersion(5) -> true
调用 isBadVersion(4) -> true
所以，4 是第一个错误的版本。

题目解析

本题目就是完全按照模板2进行即可找寻错误版本左边界，第一错误版本之后肯定全都是错误版本，因此如果二分找到找到一个错误版本，那么一定是在该版本之前继续寻找是否有错误版本。

解法(Java+Go版本)

/* The isBadVersion API is defined in the parent class VersionControl.
      boolean isBadVersion(int version); */

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int left = 1;
        int right= n;
        int mid;
        while(left<right){
            mid = left + (right-left)/2;
            if(!isBadVersion(mid))
                left = mid+1;
            else
                right = mid;
        }
        return left;
    }
}

/** 
 * Forward declaration of isBadVersion API.
 * @param   version   your guess about first bad version
 * @return            true if current version is bad 
 *                    false if current version is good
 * func isBadVersion(version int) bool;
 */

func firstBadVersion(n int) int {
    left, right := 1, n
    for left < right{
        mid := left + (right - left)/2
        if isBadVersion(mid){
            right = mid
        }else{
            left = mid + 1
        }
    }
    return left
}

二分查找模板３

模板（Java+Go版本）

public class BinarySearch {
    public static int binarySearch(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        int mid;
        while(left + 1 < right) {
            mid = left + (right - left)/2;
            if(nums[mid] == target) return mid;
            if(nums[mid] > target) right = mid;
            if(nums[mid] < target) left = mid;
        }
        if(nums[left] == target) return left;
        if(nums[right] == target) return right;
        return -1;
    }

    public static void main(String[] args) {
        int[]nums = {1,2,3,4,5,6,7,7,8,8};
        System.out.print("array: ");
        for(int num : nums) {
            System.out.print(num+" ");
        }
        System.out.println();
        int number = 5;
        System.out.printf("BinarySearch %d in this array, index: %d\n",number, binarySearch(nums,number));
        number = 7;
        System.out.printf("BinarySearch %d in this array, index: %d\n",number, binarySearch(nums,number));
    }
}

模板分析

最后一款的二分查找模板相当于保留了两个指针，模板3相对较灵活，可以说是模板2的进阶，可以定左侧边界也可以定右侧边界。
选择定左侧边界还是右侧边界只需要改变匹配到target的时候赋值即可:

            if(nums[mid] == target) return mid;
            if(nums[mid] == target) left =  mid;//确定右侧边界
            if(nums[mid] == target) right =  mid;//确定左侧边界

并且left与right相差1,因此相当于提供了两个指针方便进行其他操作处理

模板语法

起始条件: left = 0, right = length(nums) - 1
终止条件: left + 1 > right
继续查找左侧区间: right = mid
继续查找右侧区间: left = mid
保留值: left, right

分析

为什么继续查找,left,right都不再进行操作

从起始条件可以看出，每次二分查找的区间为[left, right]，即区间左右均闭合。
在target与nums[mid]进行比较时，定边界需要保留边界值即所以不再进行加减操作是为了让左侧区间和右侧区间分别改变为[left, mid]和[mid, right]以保留边界位置。这里不需要担心死循环的问题，因为终止条件说明left,right无法相等因而不会有死循环的可能。

模板例题

LeetCode 658. 找到 K 个最接近的元素

具体问题

给定一个排序好的数组，两个整数 k 和 x，从数组中找到最靠近 x（两数之差最小）的 k 个数。返回的结果必须要是按升序排好的。如果有两个数与 x 的差值一样，优先选择数值较小的那个数。
示例 1:
输入: [1,2,3,4,5], k=4, x=3
输出: [1,2,3,4]
示例 2:
输入: [1,2,3,4,5], k=4, x=-1
输出: [1,2,3,4]
说明:
k 的值为正数，且总是小于给定排序数组的长度。
数组不为空，且长度不超过 104
数组里的每个元素与 x 的绝对值不超过 104

题目解析

本题目第一步找到距离靠近x最小的数字位置以及保留前一位或者后一位 => left, right(不是left就是right)。
第二步进行中心扩展即可找到k个数。

解法(Java+Go版本)

class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
    List<Integer>nums  = new LinkedList();
    if (arr.length == 1){
        nums.add(arr[0]);
        return nums;
    }
    int left = 0, right = arr.length - 1;
    while(left + 1 < right ){
        int mid = left + (right - left)/2;
        if (x <= arr[mid])
            right = mid;
        else 
            left = mid;
    }

    int i = left, j = right; 
    while(nums.size() < k){
        if (j == arr.length || (i >= 0 &&  x - arr[i]  <= arr[j] - x)){
            nums.add(0, arr[i]);
            i--;
        }else{
            nums.add(arr[j]);
            j++;
        }
    }
    return nums;
    }
}

func findClosestElements(arr []int, k int, x int) []int {
    if len(arr) == 1{
        return arr
     }
    left, right := 0, len(arr) - 1
    for left + 1 < right {
        mid := left + (right - left)/2
        if  x <= arr[mid] {
            right = mid
        } else {
            left = mid
        }
    }

    var nums []int
    i, j := left, right
    for len(nums) < k{
        if j == len(arr) || (i >= 0 &&  x - arr[i]  <= arr[j] - x) {//在right之后一定大于等于x,在left之前一定小于等于x，且没到数组首端
            nums = append([]int{arr[i]}, nums[:]...)
            i--
        }else if j < len(arr) {//没到数组尾端时
            nums = append(nums, arr[j])
            j++
        }
    }
    return nums
}

总结

二分查找主要难点在于：

起始条件 left,right的取值，一般若闭合区间，则0, length(nums)。如果涉及边界位置代入计算，则0,length(nums)。
循环条件，如三中末班分析，第一要能够避免死循环，第二要看保留值（保留边界）问题，left <= right 无值保留，left < right则会剩下left = right一个位置，如果left + 1 < right 则会剩下left, right (right = left + 1)两个位置。
向左向右查找区间：如果是需要保留当前mid作为边界则赋值为mid，否则相应进行+1、-1操作；另外注意避免死循环问题即可，根据具体来定是否进行+1、-1操作。

如上即是我所认知的二分查找，码字不易，多多点赞转发支持，谢谢。人总是要逼自己一把，继续加油。

作者：涓涓清泉
链接：https://juejin.cn/post/6919408716236193800
来源：掘金

数据结构与算法之二分查找三模板

二分查找模板１

模板分析

模板语法

分析

模板例题

二分查找模板２

模板分析

模板语法

分析

模板例题

二分查找模板３

模板分析

模板语法

分析

模板例题

总结

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

数据结构和算法分析