前言

增删改查(CRUD)是每个数据结构内容都不可或缺的部分

本篇主要来分析一下查找算法。往往在真是的算法题中查找是非常难的一个问题，因为简单的有顺序查找，难的有深度和广度。更重要的是，本身它是需要结合数据结构的，所以它的考察是面试中比较重要的一项，也是面试官比较喜欢的。本篇将罗列一些算法结合数据结构进行分析。如果你喜欢我的文章，欢迎评论，欢迎Star~。欢迎关注我的github博客

正文

一般我们大多在使用的查找方式是顺序查找。

对于一个数组而言，我们会使用遍历数组的方式：

def find(arr, item):
  for index in range(0, len(arr)):
     if arr[index] == item:
        return index;

这种方式，在最坏的情况下(想要找的数在最后一个)，时间复杂度是在O(n)，比较不稳定。

而对于一个顺序列表(排序好的)来说，我们可以使用折半查找的方式：

def binary_Search(arr, item):
    found = False
    first = 0
    last = len(arr) - 1
    loc = 0
    while first <= last and found == False:
        loc = (first + last) / 2
        if item < arr[loc]:
            last = loc - 1
        elif item > arr[loc]:
            first = loc + 1
        else:
            found = True
            break
    if(found): print 'this item\'s index is ' + str(loc)
    else: print 'not found'

laizimo / zimo-article

查找算法总结 #30

前言

正文