有序查找，无序查找，二分查找总结

无序查找

其实大部分的查找方法，都是通过先定义初始的 found=False，然后一旦查找到之后，found变为True：

def sequential(alist,item):
    pos=0
    found=False
    while pos<len(alist) and not found:
        if alist[pos]==item:
            found=True
        else:
            pos=pos+1
        return found
print(sequential([1,3,5],2))

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
 

有序查找

在最好的情况下，有序查找只需要比较一次就能知道目标元素不在列表中，平均情况下需要比较n/2次，不过算法的复杂度仍然是O（n）。总之，只有当列表中不存在目标元素时，有序查找才会提高查找的速率。

def youxu(alist,item):
    pos=0
    found=False
    stop=False
    while pos<len(alist) and not found and not stop:
        if alist[pos]==item:
            found=True
        else:
            if alist[pos]>item:
                stop=True
            else:
                pos=pos+1
    return found
print(youxu([1,3,5,7],3))

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
 

二分查找

先从中间查找，如果目标元素大，则在右面找；反之在左边找：

def erfenchazhao(alist,item):
    first=0
    last=len(alist)-1
    found=False
    while first <=last and not found:
        midpoint=(first+last)//2
        print(midpoint)
        if alist[midpoint] == item:
            found = True
        else:
            if item<alist[midpoint]:
                last =midpoint -1
            else:
                first=midpoint+1
    return found
print(erfenchazhao([1,5,6,7,9],5))

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
 

文章来源: xuyipeng.blog.csdn.net，作者：是Dream呀，版权归原作者所有，如需转载，请联系作者。

原文链接：xuyipeng.blog.csdn.net/article/details/119297542