二分法查找(Binary，Search)

二分法查找，也称为折半查找，顾名思义就是将查找区间二分，逐步缩小查找范围，最终找到目标元素。

二分法查找的前提是查找区间内的数据是有序的，如果是无序的，则需要先使用某种排序算法将其排序。

二分法查找的基本思路：

1. 取左右边界，计算中间位置 mid。

2. 如果目标元素等于 mid，那么直接返回 mid 索引；

3. 如果目标元素小于 mid，那么在左侧区间继续找；

4. 如果目标元素大于 mid，那么在右侧区间继续找；

5. 如果最终没有找到目标元素，则返回不存在。

下面是一个典型的二分法查找代码实现：

```python

def binary_search(arr, target):

left, right = 0, len(arr) - 1

while left <= right:

mid = left + (right - left) // 2

if arr[mid] == target:

return mid

elif arr[mid] > target:

right = mid - 1

else:

left = mid + 1

return -1

```

使用上面的代码，可以在一个有序数组中查找目标元素的位置（若存在），如果目标元素不存在，则返回 -1。

二分法查找的时间复杂度是 O(log n)，因为每次查找都能够将查找范围缩小一半，所以效率较高。

下面是一个案例：

假设有一个长度为 100 的有序数组，每个元素的值是它的下标。例如，arr[0] = 0，arr[1] = 1，arr[2] = 2，依此类推。现在要查找元素为 75 的位置。

```python

arr = [i for i in range(100)]

target = 75

result = binary_search(arr, target)

if result == -1:

print("元素不存在！")

else:

print("元素第一次出现的位置是：", result)

```

输出结果为：“元素第一次出现的位置是： 75”，表示目标元素在数组中的下标为 75。

总之，二分法查找的思路简单，效率高，适用于查找区间较大，但数据有序的情况。 如果你喜欢我们三七知识分享网站的文章， 欢迎您分享或收藏知识分享网站文章 欢迎您到我们的网站逛逛喔！https://www.37seo.cn/