二分查找

二分查找

  • 二分查找只可以作用在有序序列中。

  • 循环low版

    def find(alist,item):#alist是一个有序序列,item是我们要在alist中查找的元素
        find = False
        low = 0
        high = len(alist)-1
        
        while low <= high:
            mid = (low + high) // 2 #中间元素的下标
    
            if item < alist[mid]:#查找的元素<中间元素,查找的元素存在中间元素左侧
                #将中间元素左侧序列作为一个新的序列,然后再基于item和当前新序列的中间值进行大小比较
                high = mid - 1 #low和high就可以表示新序列的范围
            elif item > alist[mid]:#查找的元素存在于中间元素右侧
                low = mid + 1 #low和high就可以表示中间元素右侧的子序列
            else:#查找的元素就是中间元素
                find = True
                break
        
        return find
    
    alist = [1,3,4,5,33,55]  #有序序列并不是连续序列
    print(find(alist,33))
    #True
    #print(find(alist,9))
    #False
    #上面的代码只适用于正序的有序序列,如果是倒序的只需要将high = mid - 1  和low = mid + 1  互换地方即可
    

递归版

def find1(alist,item,low=0,high =len(alist)): #问题1,为什么len(alist),而不减1
 
        aim = (low+high) // 2
        if not alist[low:high]:  #问题2 这写法什么意思
            return "没找到"
        
        if item < alist[aim]:
            high = aim -1     
            return find1(alist,item,low,high)  #问题三,renturn得到什么
            
        elif item > alist[aim]:
            low = aim +1 
            return find1(alist,item,low,high)
        else:
            return "找到了"
  
#alist = [1,2,3,4,5]
print(find1(alist,5))
Ture

补充:
 问题1: alist[low:high] 如果切片相等也是空,这是为了结束递归放置的条件。切片[4:4]或[5:4]都是空,这样就终止了alist,因为需要当high = low 也要走下边的代码,如果你是len(alist)-1的话,有的部分找不到。
 问题2:如上,就是判断条件,比较高级的写法。说白了就是low<high 终止递归
 问题3:如果不return的话,当找到了return回来,只有一个递归能获取return返回值,后边的都是None了
 
上一篇:18. java之list集合


下一篇:排序与搜索