Press "Enter" to skip to content

Go 数据结构和算法篇(十):二分查找的变形版本

日常开发过程中,除了我们昨天讲到的正常的二分查找,还有很多二分查找的变形版本,今天开始,我们就来给大家一一介绍这些变形版本。

从给定序列中查找第一个匹配元素

符合标准的二分查找条件的序列一般是比较理想的情况,如果要查找的元素在序列中有多个怎么办?所以我们要给大家介绍的第一个常见的变形版本,就是在一个给定排序序列中查找第一个等于给定值的元素。在继续往下看之前,你不妨借机先思考一下要怎么实现。

其实关键节点就在于在序列中找到值等于待查找元素值时的处理。如果此时 mid 位置已经到了序列的最左边,不能再往左了,或者序列中索引小于 mid 的上一个元素值不等于待查找元素值,那么此时 mid 就是第一个等于待查找元素值的位置;否则还要继续往前找。

对应的 Go 实现代码如下,其他地方都一样,就是 num == nums[mid] 时的处理逻辑变了:

package main

import (
    "fmt"
)

// 二分查找变形版本1:查找第一个值等于给定值的元素
func binarySearchV1(nums []int, num, low, high int) int {
    if low > high {
        return -1
    }

    mid := (low + high) / 2
    if num < nums[mid] {
        return binarySearchV1(nums, num, low, mid - 1)
    } else if num > nums[mid] {
        return binarySearchV1(nums, num, mid + 1, high)
    } else {
        // 除了需要判断第一个与 num 相等的元素索引外,其他和普通二分查找逻辑一致
        if mid == 0 || nums[mid-1] != num {
            return mid
        } else {
            return binarySearchV1(nums, num, low, mid - 1)
        }
    }
}

func main() {
    nums := []int{1, 2, 3, 3, 4, 5, 6}
    num := 3
    index := binarySearchV1(nums, num, 0, len(nums) - 1)
    if index != -1 {
        fmt.Printf("Find num %d first at index %d\n", num, index)
    } else {
        fmt.Printf("Num %d not exists in nums\n", num)
    }
}

运行上述代码,打印结果如下:

-w615

从给定序列中查找最后一个匹配元素

既然有第一个等于给定值的查询,自然就有最后一个等于给定值的查询,这就是二分查找的第二个变形版本:在给定已排序序列中查找最后一个等于给定值的元素。

实现逻辑和上面类似,只需要改动 num == nums[mid] 时的处理逻辑,只是这时的条件变成了 mid 位置到了序列的最右边,不能再往后了,或者索引大于 mid 的后一个元素值不等于待查找元素,才返回 mid,否则,还要继续往后找。

下面我来给出查找最后一个等于给定值的元素的 Go 实现代码:

package main

import "fmt"

// 二分查找变形版本2:查找最后一个值等于给定值的元素
func binarySearchV2(nums []int, num, low, high int) int {
    if low > high {
        return -1
    }

    mid := (low + high) / 2
    if num < nums[mid] {
        return binarySearchV2(nums, num, low, mid - 1)
    } else if num > nums[mid] {
        return binarySearchV2(nums, num, mid + 1, high)
    } else {
        // 除了需要判断最后一个与 num 相等的元素索引外,其他和普通二分查找逻辑一致
        if mid == len(nums) - 1 || nums[mid + 1] != num {
            return mid
        } else {
            return binarySearchV2(nums, num, mid + 1, high)
        }
    }
}

func main() {
    nums := []int{1, 2, 3, 3, 4, 5, 6}
    num := 3
    index := binarySearchV2(nums, num, 0, len(nums) - 1)
    if index != -1 {
        fmt.Printf("Find num %d last at index %d\n", num, index)
    } else {
        fmt.Printf("Num %d not exists in nums\n", num)
    }
}

运行上述代码,打印结果如下:

-w609

在给定序列中查找第一个大于等于给定值的元素

二分查找的第三个变形版本是:在给定排序序列中查找第一个大于等于给定值的元素。

有了前面的基础,来解决这个问题,是不是很简单?所不同的是判断节点不一样了,我们之前的需求都是查找等于给定值,现在变成了大于等于给定值,所以我们要在 nums[mid] >= num 这个判断条件上做文章,思路还是和之前两个变形版本类似,当 mid 已经是最左边的元素,或者 mid 的前一个元素值小于给定查询值,则 mid 对应元素即为满足条件的元素,否则继续往前查找。

对应的 Go 实现代码如下:

package main

import "fmt"

// 二分查找变形版本3:查找第一个大于等于给定值的元素
func binarySearchV3(nums []int, num, low, high int) int {
    if low > high {
        return -1
    }

    mid := (low + high) / 2
    if num <= nums[mid] {
        // 判断条件变更,找到第一个大于等于给定值的元素
        // 最左侧元素值,或者当前 mid 位置前一个元素值小于给定值
        if mid == 0 || nums[mid-1] < num {
            return mid
        } else {
            return binarySearchV3(nums, num, low, mid-1)
        }
    } else {
        return binarySearchV3(nums, num, mid+1, high)
    }
}

func main()  {
    nums := []int{1, 2, 3, 3, 4, 5, 6}
    num := 3
    index := binarySearchV3(nums, num, 0, len(nums) - 1)
    if index != -1 {
        fmt.Printf("Find first num greater or equal than %d at index %d\n", num, index)
    } else {
        fmt.Printf("Num %d not exists in nums\n", num)
    }
}

运行上述代码,打印结果如下:

-w684

在给定序列中查找最后一个小于等于给定值的元素

与之相对的,还有我们最后要讨论的一个二分查找的变形版本:在给定序列中查找最后一个小于等于给定值的元素。

有了前面几个变形版本的铺垫,相信你自己就可以写出对应的实现代码了。这次的判断节点变成了 nums[mid] <= num,其中 num 是待查找的元素值,当 mid 已经是最后一个元素索引,或者 mid 的后一个元素值大于 num 则当前 mid 对应元素就是要查找的元素,否则要继续往后查找。

对应的 Go 实现代码如下:

package main

import "fmt"

// 二分查找变形版本4:查找最后一个小于等于给定值的元素
func binarySearchV4(nums []int, num, low, high int) int {
    if low > high {
        return -1
    }

    mid := (low + high) / 2
    if num >= nums[mid] {
        // 判断条件变更,找到最后一个小于等于给定值的元素
        // 最右侧元素值,或者当前 mid 位置后一个元素值大于给定值
        if mid == len(nums) - 1 || nums[mid + 1] > num {
            return mid
        } else {
            return binarySearchV4(nums, num, mid + 1, high)
        }
    } else {
        return binarySearchV4(nums, num, low, mid - 1)
    }
}

func main() {
    nums:= []int{1, 2, 3, 3, 4, 5, 6}
    num := 3
    index := binarySearchV4(nums, num, 0, len(nums) - 1)
    if index != -1 {
        fmt.Printf("Find last num less or equal than %d at index %d\n", num, index)
    } else {
        fmt.Printf("Num %d not exists in nums\n", num)
    }
}

运行上述代码,打印结果如下:

-w706

关于二分查找及其变形版本,学院君就简单介绍到这里,所有教程代码,可以在 Github 代码仓库获取:nonfu/go-tutorial,接下来,我们将开始介绍常见的字符串匹配算法。

太烂了有点差凑活看还不错太棒了 (2 人打了分, 平均分: 4.50)
Loading...
发表评论