问题描述

已有一维数组存储了N个预先排序的整数序列。采用二分查找算法以确定整数m在该数组中的位置。如若成功定位到该元素，则需输出其对应的数组下标；若未找到，则反馈信息为“Not found!”。

问题分析

二分查找法，也就是折半查找，它是一种分而治之的策略。想象一下，我们要解决一个大问题，分治算法就是先把这大问题切成几个小块，这些小块互不影响，并且跟原问题一模一样，通过搞定这些小块，最终大问题也就迎刃而解了。二分法呢，就是把问题分成两个小问题来解决的特别方法。
不过，二分查找法有个前提，那就是你得有一个排好序的列表。

具体怎么操作呢？首先，我们得知道要在哪个范围内找。用两个标记，一个叫low，一个叫high，它们就像两条边界线，low在前面，high在后面，表示我们要搜索的这片区域。然后，我们找到这片区域的中间点，标记为mid。接着，拿你要找的数和中间点的数比一比。如果你要找的数更大，那就把前面的low移到mid后面，相当于扔掉前面一半不用看了；反过来，如果你要找的数更小，就把后面的high移到mid前面，也就是忽略后面一半。就这么一减半、一减半地找，直到low和high碰头，表示没地方找了，查找也就结束了。

算法设计

我们有一个按顺序排列好的数字列表，放在了一个数组里。要想找到某个数字在这个列表里的位置，首先我们知道数组的第一个位置是0，而最后一个位置是数组长度N减1，这就是指针low和high最开始时的值，分别是0和N-1。为了找到目标数字，我们不光要用到low、high这两个指针，还要加上一个中间指针mid，以及一个额外的变量k来记录我们正在查看的位置。通过改变k的值，我们就能一步步判断目标数字m是不是在数组里面了。

现在，让我们通过一个简单的图解方式，来理解怎么用“二分查找法”找数字。想象一下数组里这样排着数字：5, 13, 19, 21, 37, 56, 64, 75, 80, 88, 92，我们要找的数字m是21。按照二分查找的规则，一开始，low指针指向数组的第一个数字5，high指针指向最后一个数字92。然后，我们计算中间位置mid，它就是low和high指针位置相加后除以2，这里mid就会指向数字56。下面是一个简化的示意过程：

变量m里面的数字是21，我们要找的指针mid指向的是数字56。因为21比56小，按照二分查找的方法，我们知道接下来只需要在mid指的数字前面这一块找就行了，也就是在数字5到37之间。之前，指针high是指向列表最后一个元素的，但现在它要指向mid前面一个位置，也就是mid-1的位置。然后，我们得重新算一下mid应该指向哪里。简单来说，就是这样的一个过程：

再次进行比较，21大于19，现在比较范围再次转移到mid所指元素的后面，low元素所指元素下标由0变为mid+1。示意如下：

当前mid所指元素的值为21，与要查找的整数值相同，故查找成功，所查元素在表中的序号等于指针mid的值。

完整代码


def binary_search(arr, target):
    """
    在一个有序的整数列表中执行二分查找，以找到目标值的索引。
    
    参数：
        arr：一个包含整数的已排序列表
        target：要查找的目标整数
        
    返回值：
        如果目标值在列表中找到，则返回其索引；否则返回 -1
    """
    low = 0
    high = len(arr) - 1
    
    while low <= high:
        mid = (low + high) // 2
        if target < arr[mid]:
            high = mid - 1
        elif target > arr[mid]:
            low = mid + 1
        else:
            return mid
    
    return -1

def main():

    # Define the array
    a = [-3, 4, 7, 9, 13, 45, 67, 89, 100, 180]

    # Output the data in the array
    print("a数组中的数据如下：")
    for i in a:
        print(i, end=" ")
    print()

    # Input validation
    while True:
        try:
            m = int(input("Enter m = : "))  # Variable m is the integer to search for
            break
        except ValueError:
            print("请输入一个整数！")

    # Perform binary search
    k = binary_search(a, m)

    # Output result
    if k >= 0:
        print("m = %d, index = %d" % (m, k))
    else:
        print("Not be found!")

if __name__ == "__main__":
    main()

运行结果

在vscode下运行程序，结果下图所示。