推荐|Python-VBA编程500例-005-02(入门级)

1、二分查找(查找边界值)：

1-1、Python：

1-2、VBA：

个人主页：非风V非雨-CSDN博客

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

二分查找(Binary search)是一种非常高效的查找算法，主要用于在有序数组中查找特定元素的位置。具体应用包括以下几种：

1、验证存在性：对于有序数组，可以使用二分查找来确定某个元素是否存在，如果存在则返回其索引，否则返回-1。

2、查找边界值：对于有序数组中包含重复元素的情况，可以使用二分查找来确定某个元素第一次或最后一次出现的位置。通过修改二分查找的判断条件，可以实现这个功能。

3. 查找插入位置：如果要向有序数组中插入一个元素，可以使用二分查找来确定插入的位置。如果元素已经存在，则返回其索引；如果元素不存在，则返回应该插入的位置。

4. 查找最接近的元素：对于有序数组，可以使用二分查找来找到最接近某个给定值的元素。通过不断缩小查找范围，并记录最接近的元素，最终可以找到目标元素。

总的来说，二分查找适用于在有序数组中进行查找、插入和判断等操作，可以快速确定元素的位置，提高查找效率。

1、二分查找(查找边界值)：

1-1、Python：


# 1.问题描述：
# 给定一个排序的整数数组和一个要查找的目标整数target，如果target不存在于数组中，返回-1；如果target存在于数组中，则返回target在数组中出现第1次和最后1次所在的位置.
# 2.问题示例：
# 输入数组[3,5,6,8,10,10,11,24]和目标整数10，则返回目标整数第1次、最后1次所在位置(4,5)；输入数组[3,5,6,8,10,10,11,24]和目标整数7，则返回-1;
# 输入数组[3,5,6,8,10,10,11,24]和目标整数8，则返回目标整数第1次所在位置3.
# 3.代码实现:
class Solution:
    def binary_Search_Bounds(nums, target):
        left, right = 0, len(nums) - 1
        first, last = -1, -1
        if target in nums:
            while left <= right:
                mid = (left + right) // 2
                if nums[mid] == target:
                    first = mid
                    while first > 0 and nums[first - 1] == target:
                        first -= 1
                    last = mid
                    while last < len(nums) - 1 and nums[last + 1] == target:
                        last += 1
                    break
                elif nums[mid] < target:
                    left = mid + 1
                else:
                    right = mid - 1
            return (first, last) if first != last else first
        else:
            return -1
# 主函数
if __name__ == '__main__':
    solution =Solution()
    nums = [3, 5, 6, 8, 10, 10, 11, 24]
    target = 7
    target_position = Solution.binary_Search_Bounds(nums, target)
    print("输入：nums=", nums, "  ", "target=", target)
    print("输出：", target_position)
# 4.运行结果：
# 输入：nums= [3, 5, 6, 8, 10, 10, 11, 24]    target= 10
# 输出： (4, 5)
# 输入：nums= [3, 5, 6, 8, 10, 10, 11, 24]    target= 7
# 输出： -1
# 输入：nums= [3, 5, 6, 8, 10, 10, 11, 24]    target= 8
# 输出： 3

1-2、VBA：


Rem 自定义函数Binary_Search_Bounds，功能：查找目标整数在有序数组中出现的位置，若存在，且只出现了1次，则返回第1次出现的位置；若存在，且出现多次，则返回第1次、最后1次出现的位置；若不存在，则返回-1
Function Binary_Search_Bounds(arr(), target As Integer) As Variant
    Dim firstPos As Integer
    Dim lastPos As Integer
    Dim i As Integer
    Dim found As Boolean
      
    firstPos = -1
    lastPos = -1
    found = False
      
    '查找第一次出现的位置
    For i = LBound(arr) To UBound(arr)
        If arr(i) = target Then
            firstPos = i
            found = True
            Exit For '如果只需要找到第一次出现的位置，可以在这退出循环
        End If
    Next i
      
    '如果找到了第一次出现的位置，继续查找最后一次出现的位置
    If found Then
        lastPos = firstPos
        For i = firstPos + 1 To UBound(arr)
            If arr(i) = target Then
                lastPos = i
            Else
                Exit For '一旦数组中的值不再等于目标值，就退出循环
            End If
        Next i
    End If
      
    '返回结果
    Binary_Search_Bounds = Array(firstPos, lastPos)
End Function
Rem 执行过程，功能：调用自定义函数Binary_Search_Bounds，并以弹窗方式输出结果
Sub TestRun()
    Dim arr() As Variant
    Dim result As Variant
    Dim target As Integer
      
    ' 初始化数组
    arr = Array(3, 5, 6, 8, 10, 10, 11, 24)
    target = CInt(Application.InputBox("请输入目标整数：", "目标整数输入"))
    If target = False Then Exit Sub
    Select Case target
        Case Is = 3, 5, 6, 8, 11, 24
            result = Binary_Search_Bounds(arr, target)
            MsgBox "目标整数 " & target & " 出现在位置 " & result(0)
        Case Is = 10
            result = Binary_Search_Bounds(arr, target)
            MsgBox "目标整数 " & target & " 第一次出现和最后一次出现的位置分别是（" & result(0) & ", " & result(1) & ")"
        Case Else
            MsgBox "目标整数 " & target & " 不在数组中，返回-1"
    End Select
End Sub