二分法查找
猜数字游戏
0-1000猜数字游戏:
普通查找:100,99,98,…,1,需要100步
二分法查找:100--->50--->25--->13--->7--->4--->2--->1
,每次猜测中间的数字(假设猜测数字是1),将余下的数字排除一半。需要7步
n个元素组成的列表,最多需要走$log_2{n}$步。普通查找n步
attention:二分法查找仅对有序列表有用
思想
折半查找,比较次数少,速度快,只能作用于有序数组和顺序表,当查找范围内只有一个数据的时候,结束查找。
最优时间复杂度:$O(1)$
最坏时间复杂度:$O(logn)$
运行时间
运行时间是通过大o()运行时间来表示
二分查找的速度比线性查找快的多,元素越多,快的越多
算法运行时间是从其增速的角度来度量的
Python实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
def (alist, target) : low = 0 high = len(alist) - 1 while low <= high: mid = (low + high) // 2 guess = alist[mid] if guess == target: return mid if guess > target: high = mid - 1 else : low = mid + 1 return None def (alist, item) : n = len(alist) if n > 0 : mid = // 2 guess = alist[mid] if guess == item: return True elif guess > item: return binary_search(alist[:mid], item) elif : return binary_search(alist[mid+1 :], item) return False
1 2 3 4 5 6 7 8 9
def linear_search (alist, obj) : n = len(alist) for i range(0 , n): if alist[i] == obj: return i return "{} not in the alist" .format(obj)
选择排序
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
def findSmallest (alist) : n = len(alist) smallest = alist[0 ] smallest_index = 0 for i in range(1 , n): if alist[i] < smallest: smallest = alist[i] smallest_index = i return smallest_index def selectSort (arr) : newarr = [] n = len(arr) for i in range(n): smallest = findSmallest(arr) newarr.append(arr.pop(smallest)) return newarr
近期评论