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 = -1
End Function
Rem 执行过程，功能：通过调用自定义函数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 "输出: " & position
End Sub
'结果输出:
'输入: [3, 5, 6, 8, 10, 10, 11, 24]
'输出: 5

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