数组array包含了顺序的元素，[1,2,3,...]，查找目标元素r是否在数组中。
我们已经提前知道数组递增顺序
时间复杂度为O(logN)
递推公式：
f(N) = f(N/2) + O(1) = f(N/4) + 2 * O(1)
假设 N = 2 ^ M
最后可以推出
f(N) = O(logN)
// O(N)
def LinearSearch(array, r):
for i in range(len(array)):
if array[i] == r:
return True
return False
// O(logN)
def BinarySearch(array, r):
left = 0
right = len(array) - 1
while left <= right:
mid = int((left + right) / 2)
if array[mid] < r:
left = mid + 1
elif array[mid] > r:
right = mid - 1
else:
return True
return False
array = list(range(100000000))
import time
t1 = time.time()
LinearSearch(array, 100000001)
t2 = time.time()
print(‘线性查找：‘, t2 - t1)
t3 = time.time()
BinarySearch(array, 100000001)
t4 = time.time()
print(‘二分查找：‘, t4 - t3)
需求：
[
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
查找比如16在不在矩阵中
解法：
class Solution:
def searchMatrix(self, matrix, target):
i = 0
j = len(matrix[0]) - 1
while i < len(matrix) and j >= 0:
if matrix[i][j] == target:
return True
elif matrix[i][j] > target:
j -= 1
else:
i += 1
return False
原文：https://www.cnblogs.com/guo-s/p/12543287.html