二分法查找(Binary，Search)

二分法查找是一种高效的查找方法，适用于有序数组或有序列表。它的基本思想是将查找范围不断缩小一半，直至找到目标元素或查找范围为空。二分法查找的时间复杂度为O(log n)，其中n是数组或列表的长度。

二分法查找的具体步骤如下：

1. 首先，确定查找范围的上界和下界。通常，初始时上界为数组的最后一个元素的索引，下界为数组的第一个元素的索引。

2. 计算中间元素的索引，通过将上界和下界相加再除以2得到。如果有余数，则将其舍去。

3. 比较中间元素与目标元素的大小关系：

a. 如果中间元素等于目标元素，则找到了目标元素，返回中间元素的索引。

b. 如果中间元素大于目标元素，则更新上界为中间元素的前一个元素的索引。

c. 如果中间元素小于目标元素，则更新下界为中间元素的后一个元素的索引。

4. 重复步骤2和步骤3，直到找到目标元素或查找范围为空。

以下是一个简单的示例，演示如何使用二分法查找算法在有序数组中查找目标元素：

```python

def binary_search(arr, target):

low = 0

high = len(arr) - 1

while low <= high:

mid = (low + high) // 2

if arr[mid] == target:

return mid

elif arr[mid] > target:

high = mid - 1

else:

low = mid + 1

return -1 # 如果目标元素不存在，返回-1

# 测试

arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

target = 6

result = binary_search(arr, target)

if result != -1:

print(f"目标元素在索引 {result} 处找到。")

else:

print("目标元素不在数组中。")

```

在上述代码中，我们定义了一个`binary_search`函数，它接受一个有序数组和目标元素作为参数，返回目标元素在数组中的索引。如果目标元素不存在，函数将返回-1。

以上面的示例为例，假设我们要查找的目标元素是6。在第一次迭代中，初始上界为9，初始下界为0；计算中间元素索引为4，对应的值为5，小于目标元素6，所以更新下界为5。在第二次迭代中，上界仍为9，下界更新为5；计算中间元素索引为7，对应的值为8，小于目标元素6，所以更新下界为8。在第三次迭代中，上界仍为9，下界更新为8；计算中间元素索引为8，对应的值为9，大于目标元素6，所以更新上界为7。在第四次迭代中，上界更新为7，下界仍为8；计算中间元素索引为6，对应的值为7，大于目标元素6，所以更新上界为5。此时上界等于下界，算法结束。目标元素6在数组中的索引为5，正好找到了。

二分法查找是一种非常高效的查找算法，适用于大型的有序数组或列表。对于有序数组，二分法查找通常优于线性查找，因为它的时间复杂度为对数级别而不是线性级别。然而，二分法查找要求数组或列表是有序的，因此在进行查找之前，需要确保数据的有序性。 如果你喜欢我们三七知识分享网站的文章， 欢迎您分享或收藏知识分享网站文章 欢迎您到我们的网站逛逛喔！https://www.ynyuzhu.com/