算法图解与剑指offer - 二分查找

vlambda
2021-08-21

算法图解与剑指offer - 二分查找

一维数组二分查找

二维数组二分查找

二分查找

二分查找是一种算法，其输入是一个有序的元素列表。如果要查找的元素包含在列表中，二分查找返回其位置；否则返回null。

一维数组二分查找

题目：函数binary_search接受一个有序数组和一个元素。如果指定的元素包含在数组中，这个函数将返回其位置。

数据：一维数组（并已排序）

时间复杂度: log2n 一般而言，对于包含n个元素的列表，用二分查找最多需要log2n步（log2100相当于问“将多少个2相乘的结果为100”），而简单查找最多需要n步。

算法核心：在查找表中不断取中间元素与查找值进行比较，以二分之一的倍率进行表范围的缩小。

def binary_search(list, item): low = 0 high = len(list) -1 ## 索引来表示位置 while low <= high: mid = round((low + high) / 2.) guess = list[mid] # print(mid) if guess < item: low = mid + 1 elif guess > item: high = mid - 1 else: return mid
 return None
if __name__ == '__main__': my_list = [1, 3, 5, 7, 9, 12, 22, 45, 66, 75] Rindex = binary_search(my_list, 12) print(Rindex) print(my_list[Rindex])

二维数组二分查找

题目：在一个二维数组中找到数字7，则返回true，如果没有找到，则返回false。

数据：二维数组（并已排序）

时间复杂度：

算法核心：首先选取数组中右上角的数字。如果该数字等于要查找的数字，查找过程结束；如果该数字大于要查找的数组，剔除这个数字所在的列；如果该数字小于要查找的数字，剔除这个数字所在的行。也就是说如果要查找的数字不在数组的右上角，则每一次都在数组的查找范围中剔除一行或者一列，这样每一步都可以缩小查找的范围，直到找到要查找的数字，或者查找范围为空。

查找过程：

注：重要的两部分

1. 循环条件：

2. 判断条件以及执行内容

import numpy as np

def binary_search(arr, item): rows = arr.shape[0] cols = arr.shape[1]
 ## index row = 0 columns = cols - 1
 while (columns >= 0 and row < rows): if item == arr[row, columns]: # return ("row:"+str(row+1), "columns:"+str(columns+1)) return True elif item < arr[row, columns]: columns -= 1 else: row += 1
 return False

if __name__ == '__main__': arrTest = np.array([[1, 2, 8, 9, 14], [2, 4, 9, 12, 16], [4, 7, 10, 13, 17], [6, 8, 11, 15, 19]]) item = 7
 index = binary_search(arrTest, item) print(index)

应用：

1 数据库注释

2 根据 id 提取序列

3 查找数据

参考：

书籍《算法图解》

书籍《剑指offer》

vlambda博客
学习文章列表