经典算法：双指针问题--二分查找

怼烎@ 2023-03-01 11:53 5阅读 0赞

**算法—程序的灵魂，没错就是灵魂** ！

今天我们来聊聊关于双指针问题中的二分查找的问题

> 内容参考：《你也能看得懂的Python算法书》  
> 转载请标注： https://blog.csdn.net/qq\_43582207  
> python版本：Python3.7  
> IDE：Jupyter notebook  
> 作者:My apologize

### 文章目录 ###

*  双指针问题
 *   *  二分查找
     *  猜数字小程序

# 双指针问题 #

## 二分查找 ##

<<关于有序数组，还有一个经典问题，如何在一个有序数组中精确找到一个元素的位置。>>

第一种笨办法：依次从第一个元素遍历到最后一个，最多需要遍历n次，这种方法会使耗时大大增加。当整个序列中元素非常多时，二分查找的优势就很明显。

如果有同学还不清楚什么是二分查找法，所谓二分查找法，每次查找后，查找的范围都折半。

要解决这个问题，引入一个概念指针，本题需要两个指针，头指针（head)和尾指针(tail),头指针是指向序列第一个元素（第一个元素的下标），而指向最后一个元素的后方叫尾指针（最后一个元素的下标加一）（**注意是后方而不是指向最后一个元素**）

**举个例子：**  
*变 量 说 明*：

**search:需要被查找的元素  
head:头指针  
tail:尾指针  
mid:中间位置下标  
ans:search在序列中的下标**

1.有一个有序数组numbers = \[1, 3, 5, 6, 7, 13, 54, 77, 100\]，里面有9个元素。  
假设要查找的数字是 7(search) 首先先得到这个序列的中间位置元素，作为初始比较的元素，中间元素的下标为mid,而**mid = (head + tail) // 2** , 让numbes\[mid\]和需要被查找的数search进行比较如果相等那就直接找到，得到需要被查找元素的下标ans

if search == numbers[mid]:
    	ans =mid
    	print('被查找的元素下标为:' + ans)

2.如果search比中间位置数大，则说明search在中间数之后，所以可以缩小查找范围，不大于中间数的部分就不用查找了，肯定也比search小。所以把mid+1当作新的头指针，尾指针不变，这样新的mid就在新的范围中产生离需要查找的ans更接近

if search > numbers[mid]:
    	head = mid + 1

3.如果search比中间位置数小，类比2，将mid当作尾指针，缩小查找范围

if search < numbers[mid]:
    	tail = mid

4.如果不断地缩小范围直到尾指针正好比头指针大1时,头指针和尾指针之间只剩一个元素时，就不需要再求mid去比较，而是直接把这个仅剩的元素去和search比较，如果相等，那这个元素就是search,反之就是这个序列里没有这个search元素

while tail - head > 1:
    	.......
    else:
    	if search == numbers[head]:
    		ans = head
    	else:
    		ans = -1
    		print('没有找到' + search + '这个数字')

按照上面的思路我完整地写一遍代码：

numbers = [1, 3, 5, 6, 7, 13, 54, 77, 100]
    head, tail = 0, len(numbers)# 设置头尾指针初始值
    search = eval(input('Please enter a number to search: '))
    
    while tail - head > 1:# 当头指针减尾指针为1时，查找范围内就只有head指向的数
        mid = (head+tail)//2
        if search > numbers[mid]:
            head = mid + 1
        if search < numbers[mid]:
            tail = mid
        if search == numbers[mid]:
            ans = mid
            break # 找到元素下标结束
    else: # while循环完整完成，运行此语句块
        if search == numbers[head]:
            ans = head
        else:
            ans = -1
    print(ans)

可直接运行，你可以输入随意数字，或者更改数组中元素来测试。

=========================================================

## 猜数字小程序 ##

介绍完了二分法查找问题，我有了另外一个问题，既然二分法耗时少，查找次数少， **但有没有查找次数的上限？**

**没错！** 数学上告诉我们二分查找法有最大查找次数，当n个数字，那它最大查找次数就是logn,那这个如何在计算机中验证呢？

***我 写 了 一 个 猜 数 字 的 程 序***：

用二分查找法，让电脑获取随机数字作为要猜的数字，然后电脑每次都猜\*\*（最大值+最小值）/2**的那个值，根据反馈的结果大小继续查找，直到找到结果。通过二分查找法，每次获得的搜索范围都比以前要减小一半，当n=1000，logn的值为10，所以最多查找次数不超过**10\*\*次，我们来检验一下！

第一步：编写一个二分查找法的小程序

import random
    #guessnumber.py
    #验证二分法查找法最多次数为logn
    
    "单轮测试结果"
    target = random.randint(1,1000)# 随机获得一个1-1000之内的整数作为要被猜的数字
    print("target= %d"%target)
    guess = random.randint(1,1000)# 随机获得一个1-1000之内的整数作为第一次尝试猜测的数字
    count = 0# 赋猜测次数初始值为0次
    max = 1000# 赋最大值初始值
    min = 0# 赋最小值初始值
    while True:
        if guess < target:
            print("guess%d= %d is smaller than target"%(count,guess))
            min = guess# 猜测数字小了，将此次猜测结果赋给min,作为下次最小值
            guess = (guess + max)//2
            count += 1
        elif guess > target:
            print("guess%d= %d is bigger than target"%(count,guess))
            max = guess# 猜测数字大了，将此次猜测结果赋给max,作为下次最大值
            guess = (min + guess)//2
            count += 1
        else:
            print("guess%d= %d is right!"%(count,guess))
            break
    print("Total number is %d"%count)

测试结果截图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTgyMjA3_size_16_color_FFFFFF_t_70]  
由图可见，次数为8次，确实不超过10次就查找到了准确值。  
可这只是一次测试，会不会是偶然，所以要设计一个循环在多次测试中统计结果判断是否都在10次之内。

第二步：编写一个循环测试100次二分查找法的小程序  
ps:为了方便我把第一步的程序封装起来，并且为了显示结果简单，删除了每次打印每次输出结果。直接输出最后成功次数。

import random
    #guessnumber.py
    #验证二分法查找法最多次数为logn
    
    
    def binary_search():
        "单轮测试结果"
        target = random.randint(1,1000)# 随机获得一个1-1000之内的整数作为要被猜的数字
        # print("target= %d"%target)
        guess = random.randint(1,1000)# 随机获得一个1-1000之内的整数作为第一次尝试猜测的数字
        count = 0# 赋猜测次数初始值为0次
        max = 1000# 赋最大值初始值
        min = 0# 赋最小值初始值
        while True:
            if guess < target:
                # print("guess%d= %d is smaller than target"%(count,guess))
                min = guess# 猜测数字小了，将此次猜测结果赋给min,作为下次最小值
                guess = (guess + max)//2
                count += 1
            elif guess > target:
                # print("guess%d= %d is bigger than target"%(count,guess))
                max = guess# 猜测数字大了，将此次猜测结果赋给max,作为下次最大值
                guess = (min + guess)//2
                count += 1
            else:
                # print("guess%d= %d is right!"%(count,guess))
                break
        # print("Total number is %d"%count)
        if count <= 10:
            return True# 在10次之内返回真
        else:
            return False# 返回假
    
    rcount = 0# 测试成功次数初始值0
    ecount = 0# 测试失败次数初始值0
    for i in range(100):
        if binary_search():
            rcount += 1
        else:
            ecount += 1
    print("success_number：%d,fail_number：%d"%(rcount,ecount))

测试结果：  
![在这里插入图片描述][20200710102201786.png]

就是这样一个简单程序，相信大家对二分法有了一定的了解。

=========================================================

\*\*\*p y t h o n 经 典 算 法 持 续 更 新 中 ， 明天 预 告 ： 链 表

///感兴趣的朋友，点个关注，学习不迷路！///\*\*\*

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTgyMjA3_size_16_color_FFFFFF_t_70]: /images/20230208/8783361798dc4671aece966c8939ac4b.png
[20200710102201786.png]: /images/20230208/ffdce656fd2c4199a8de63e79679e2f5.png