查找算法有哪些
查找算法是用于在数据集合中查找特定元素的算法，根据不同的数据结构和效率要求，有多种查找算法。以下是一些常见的查找算法：
顺序查找（Sequential Search）
原理：逐个遍历数据集来查找目标元素。
时间复杂度：O（n）。
适用场景：适用于无序的数据集合。
代码示例：
```python
def linearSearch（arr, val）:
for i in range（len（arr））:
if arr[i] == val:
return i
return -1
```
二分查找（Binary Search）
原理：在有序数据集合中，从中间位置作为起点不断划分区间并查找。
时间复杂度：O（log n）。
适用场景：适用于有序的数据集合。
代码示例：
```python
def binarySearch（arr, low, high, val）:
while low <= high:
mid = （low + high） // 2
if arr[mid] == val:
return mid
elif arr[mid] < val> low = mid + 1
else:
high = mid - 1
return -1
```
插值查找（Interpolation Search）
原理：在有序数据集合中，根据目标元素与数据集合首尾之间的差值，利用插值估算目标元素的位置。
时间复杂度：O（log log n）或O（n）。
适用场景：适用于均匀分布的有序数据集合。
代码示例：
```python
def interpolationSearch（arr, val）:
low = 0
high = len（arr） - 1
while low <= high and val >= arr[low] and val <= arr[high]:
if low == high:
if arr[low] == val:
return low
return -1
pos = low + int（（（float（high - low） / （arr[high] - arr[low]）） * （val - arr[low]）））
if arr[pos] == val:
return pos
if arr[pos] < val> low = pos + 1
else:
high = pos - 1
return -1
```
斐波那契查找（Fibonacci Search）
原理：在有序数据集合中，根据斐波那契数列调整中间点的位置来查找。
时间复杂度：O（log n）。
适用场景：适用于有序的数据集合。
代码示例：
```python
def fibonacciSearch（arr, val）:
fib2 = 0
fib1 = 1
fibm = fib2 + fib1
while fibm < len> fib2 = fib1
fib1 = fibm
fibm = fib2 + fib1
offset = -1
while fibm > 1:
i = min（offset + fib2, len（arr） - 1）
if arr[i] < val> fibm = fib1
fib1 = fib2
fib2 = fibm - fib1
offset = i
elif arr[i] > val:
fibm = fib2
fib1 = fib1 - fib2
fib2 = fibm - fib1
else:
return i
if fib1 and offset + 1 < len xss=removed> return offset + 1
return -1
```
B树查找（B-Tree Search）
原理：在平衡的B树中查找元素。
时间复杂度：O（log n）。
适用场景：适用于B树数据结构。
代码示例：