二分搜索

计算机算法中有两个大类：搜索、排序。在学习查找算法时，我们首先学习的就是二分搜索，下面就是我对二分搜索的一些理解：
二分搜索作为一个基础查找算法，适用于列表中查找数据，其时间复杂度为O(log2n)，但是，该方法有着一个弊端就是需要列表内的数据是按顺序由小到大进行排列的，因此，可参照我的其他文章了解排序算法。
二分搜索的原理很简单，对一个有序序列进行搜索，在搜索过程中，先确定左右指针（left，right）每次取中间数（mid）的值与目标值（value）进行比较，若mid值大于目标值（value），则将右指针（right）放与mid指针左边即mid - 1处，反之，若mid值小于目标值（value），则将左指针（left）放与mid指针右边即mid + 1处。最终，若判定到mid指针处的值为目标值（value），则返回此时mid指针位置。

代码如下：

def binary_search(Inp_list,val):  #定义二分搜索函数，两个参数为待搜索列表和目标值
   left = 0  #左指针初始位置为0
   right = len(Inp_list) - 1  #右指针初始位置为最右侧数位置
   while right >= left:  
        mid = (left + right) // 2  #mid指针位置为left与right中间值
        if Inp_list[mid] == val:  
            return mid  
        else:  
            if Inp_list[mid] > val:  
                right = mid - 1  
            else:  
                left = mid + 1

在创建列表时，Python不像C语言那样创建数组，Python中的数组是以列表形式呈现，若手动输入数字需使用Python的列表生成式，代码如下。

list1 = [int(n) for n in input().split()]

最后可进行测试，不要忘记传入参数。
注意：

• 1.在Python中，若两数相除取整数位应为‘ // ’，这点与C语言不同。
• 2.在Python中是没有指针的，文章中所说只是方便理解，请见谅。