查找算法
在LeetCode刷题或者面试过程中发现，查找问题一直是不可避免的。对任何数据结构的遍历过程无非就是查找过程。
我们需要针对某些数据结构的特点如何正确地、高效地进行查找，而查找的过程最需要注意边界控制。
下面以二分查找为例。
1. 二分查找★★☆
目的：在一个含有N个元素的有序数组中有效地的定位目标值。
思想：假设在有序数组arr中查找元素k，返回k所在的下标（索引值）。设arr[low,high]是当前的查找区间，确定该区间的中间位置 m i d = ⌊ ( l o w + h i g h ) / / 2 ⌋ mid=⌊(low+high)//2⌋ mid=⌊(low+high)//2⌋，然后将待查的k值与arr[mid]比较:
- 若
k==arr[mid]，说明找到k，则查找成功并且终止。 - 若
k<arr[mid]，根据数组有序的前提，目标值k在左边的区域中，索引的范围改为[low, mid-1] - 若
k>arr[mid]，目标值在右边的区域中，查找索引范围改为[mid+1, high]。
时间复杂度： O ( l o g 2 n ) O(log_2n) O(log2n)
代码实现
# -*- coding: utf-8 -*- # @Time : 2020-04-11 23:28 # @Author : yuzhou_1su # @File : Binary_Search.py # @Software : PyCharm def binary_search1(arr, item): """ 二分查找的非递归实现1 :param arr: 有序数组 :param item: 待查元素 :return: 找到待查元素的所有；如果找不到，则返回None """ low = 0 high = len(arr) - 1 # 注意此处，high索引能取到 while low <= high: # 条件是low<=high，区间中没有元素时结束 mid = (low + high) // 2 curr_item = arr[mid] if curr_item == item: return mid elif item < curr_item: high = mid - 1 # high = mid - 1 else: low = mid + 1 return None def binary_search2(arr, item): """ 左边界为n的二分查找 :param arr: 给定一个有序数组 :param item: 待查找的元素 :return: 找到待查元素的所有；如果找不到，则返回None """ low = 0 high = len(arr) # 此处 high的索引不能取到 while low < high: # 条件是low<high,区间中有一个元素时也结束 mid = (low + high) // 2 if arr[mid] == item: return mid elif item < arr[mid]: high = mid # high = mid else: low = mid + 1 return None def binary_search3_by_recursion(arr, item, low, high): """ 二分查找的递归实现 :param arr: 给定一个有序数组 :param item: 待查找的元素 :param low: 左边界 :param high: 右边界 :return: 找到待查元素的所有；如果找不到，则返回None """ # 递归终止条件 if low > high: return None mid = low + (high - low) // 2 if arr[mid] == item: return mid elif arr[mid] > item: return binary_search3_by_recursion(arr, item, low, mid-1) else: return binary_search3_by_recursion(arr, item, mid+1, high)
二分查找边界问题探讨：二分查找有几种写法？
2. 顺序查找★☆☆
如果数组无序的话，只能通过循环遍历进行查找。
时间复杂度： O ( n ) O(n) O(n)
# -*- coding: utf-8 -*- # @Time : 2020-09-09 18:06 # @Author : yuzhou_1su # @File : linear_search.py # @Software : PyCharm def linear_search(sequence, target): """线性查找 :param sequence: 待查找序列，可以无序 :param target: 待查元素 :return: 找到待查元素的所有；如果找不到，则返回None """ for i, v in enumerate(sequence): if v == target: return i return None
3. 索引查找
增加一个索引表，索引表的每一项称为索引项，索引项的一般形式: (Key, Value)。
索引查找的过程是：先在索引表中快速查找（索引表中可以按关键字有序排序，例如采用二分查找），找到关键字，然后通过对应的地址找到主数据表中的元素。
分块查找是一种典型的索引查找，其性能介于顺序查找和二分查找之间。
