Python-VBA编程500例-028(入门级)

阅读本书更多章节>>>>

经典二分查找算法(Classic Binary Search Algorithm)(也称为折半查找算法)，是一种在有序数组中查找某一特定元素的搜索算法。它要求序列必须有序，然后通过每次比较数组中间元素与目标值，将搜索范围缩小一半，直到找到目标元素或搜索范围为空。二分查找的时间复杂度是O(logn)，这意味着即使在非常大的数据集中，查找效率也非常高。

1、字典查找：在计算机科学中，二分查找常用于字典查找。例如，如果你有一个按字母顺序排列的单词列表，并且你想找到一个特定的单词，你可以使用二分查找来快速找到它。

2、电话簿查找：如果你想在一个按姓氏排序的电话簿中找到一个特定的人，你也可以使用二分查找。

3、文件查找：在文件系统中，二分查找可以用于查找具有特定名称或属性的文件。

4、数据库查询优化：在数据库中，二分查找可以用于优化查询操作。例如，如果你想在一个大型数据库中找到一个特定的记录，你可以使用二分查找来快速找到它。

5、排序和搜索问题：在排序和搜索问题中，二分查找被广泛使用。例如，在归并排序算法中，二分查找用于将数组分成两半。

6、近似匹配：在某些情况下，可能需要找到一个近似匹配而不是精确匹配。在这种情况下，可以使用变体的二分查找，例如，斐波那契查找。

7、机器学习：在机器学习中，二分查找可以用于优化算法，例如，在线学习算法。

8、编译器和解释器：在编译器和解释器中，二分查找可以用于符号表查找和词法分析。

9、数值计算：在数值计算中，二分查找可以用于求解方程和优化算法。

1、经典二分查找：

1-1、Python：

# 1.问题描述：# 在一个排序整型数组中找目标整数，若存在，则返回目标整数在排序整型数组中的位置；反之，则返回-1.# 2.问题示例：# 输入排序整型数组int_arr = [3, 5, 6, 8, 10, 10, 11, 24]和目标整数target_int = 10，输出5；# 输入排序整型数组int_arr = [3, 5, 6, 8, 10, 10, 11, 24]和目标整数target_int = 18，输出-1.# 3.代码实现：class Solution:    # 定义一个名为find_position的方法，该方法接受一个整型数组int_arr和一个整型目标值target_int作为参数    def find_position(self, int_arr, target_int):        # 如果整型数组int_arr的长度为0，即数组为空，直接返回-1表示目标值不存在于数组中        if len(int_arr) == 0:            return -1        # 初始化搜索的起始位置为数组的第一个元素索引0        start = 0        # 初始化搜索的结束位置为数组的最后一个元素索引，即数组长度减1        end = len(int_arr) - 1        # 当起始位置小于等于结束位置时，说明搜索区间内还有元素，继续搜索        # 注意，此处兼容了排序整型数组中只有一个元素的情况        while start <= end:            # 计算数组中间位置的索引            mid = start + (end - start) // 2            # 如果中间位置上的元素等于目标值，返回该中间位置索引            if int_arr[mid] == target_int:                return mid            # 如果中间位置上的元素小于目标值，说明目标值在右侧，更新起始位置为中间位置的下一个索引            elif int_arr[mid] < target_int:                start = mid + 1            # 如果中间位置上的元素大于目标值，说明目标值在左侧，更新结束位置为中间位置的前一个索引            else:                end = mid - 1        # 如果循环结束仍未找到目标值，返回-1表示目标值不存在于数组中        return -1# 主函数if __name__ == '__main__':    # 初始化一个排序整型数组    int_arr = [3, 5, 6, 8, 10, 10, 11, 24]    # 设置要查找的目标值    target_int = 10    # 创建Solution类的实例    solution = Solution()    # 打印输入的数组    print("输入:", int_arr)    # 调用find_position方法查找目标值在数组中的位置，并打印结果    print("输出:", solution.find_position(int_arr, target_int))# 4.运行结果：# 输入: [3, 5, 6, 8, 10, 10, 11, 24]# 输出: 5

1-2、VBA：

Rem 自定义函数，功能：经典二分查找Function FindPosition(int_arr As Variant, target_int As Integer) As Integer    ' 定义变量    Dim start As Integer    Dim end_pos As Integer    Dim mid As Integer    Dim arrLength As Integer          ' 检查数组是否为空    If IsEmpty(int_arr) Then        FindPosition = -1        Exit Function    End If    ' 获取数组长度    arrLength = UBound(int_arr) - LBound(int_arr) + 1    ' 初始化搜索的起始和结束位置    start = LBound(int_arr)    end_pos = UBound(int_arr)    ' 当起始位置小于等于结束位置时，继续搜索    While start <= end_pos        ' 计算中间位置        mid = start + (end_pos - start) \ 2        ' 如果找到目标值，返回其位置        If int_arr(mid) = target_int Then            FindPosition = mid            Exit Function        ' 如果中间值小于目标值，搜索右侧        ElseIf int_arr(mid) < target_int Then            start = mid + 1        ' 如果中间值大于目标值，搜索左侧        Else            end_pos = mid - 1        End If    Wend    ' 如果循环结束仍未找到目标值，返回-1    FindPosition = -1End FunctionRem 执行过程，功能：通过调用自定义函数FindPosition，实现经典二分查找，在立即窗口中输出结果Sub TestRun()    ' 定义变量    Dim int_arr As Variant    Dim target_int As Integer    Dim position As Integer          ' 初始化一个排序整型数组    int_arr = Array(3, 5, 6, 8, 10, 10, 11, 24)    ' 设置要查找的目标值    target_int = 10    ' 调用FindPosition函数查找目标值在数组中的位置    position = FindPosition(int_arr, target_int)    ' 打印结果    Debug.Print "输入: [" & Join(int_arr, ", ") & "]"    Debug.Print "输出: " & positionEnd Sub'结果输出:'输入: [3, 5, 6, 8, 10, 10, 11, 24]'输出: 5

注意：1-2中的代码需粘贴到你的VBA编辑器中，按F5执行TestRun程序，在立即窗口中输出结果。

2、相关文章：

2-1、Python-VBA编程500例-026(入门级) 

2-2、Python-VBA编程500例-027(入门级) 

2-3、Python-VBA编程500例-029(入门级) 

2-4、Python-VBA编程500例-030(入门级) 

Myelsa的Python算法之旅(高铁直达)：Myelsa的Python算法之旅(高铁直达)-CSDN博客

欢迎访问个人主页：非风V非雨-CSDN博客

欢迎志同道合者一起交流学习，我的QQ:94509325/微信：

阅读本书更多章节>>>>

本文链接：https://www.kjpai.cn/gushi/2024-04-09/156228.html，文章来源：网络cs，作者：言安琪，版权归作者所有，如需转载请注明来源和作者，否则将追究法律责任！