二分法查找(Binary，Search)

一、介绍

二分法查找（英文名：Binary Search），又称折半查找，是一种在**有序数组**中查找目标元素的算法，其思想是将有序数组分成两部分，通过比较目标元素和中间元素的大小，来确定目标元素在哪一部分中继续查找，直到找到目标元素或者确定目标元素不存在为止。

二、使用方法

1. 算法思路

（1）在有序数组中查找目标元素，首先需要找到中间位置mid。

（2）比较目标元素和mid位置的元素大小，如果相同则直接返回mid。

（3）如果目标元素小于mid位置的元素，则在mid的左边继续查找；如果目标元素大于mid位置的元素，则在mid的右边继续查找。

（4）重复以上步骤（1）~（3），直到找到目标元素或者确定目标元素不存在为止。

2. 伪代码

```

binary_search(arr, target):

left = 0

right = len(arr) - 1

while left <= right:

mid = (left + right) // 2

if arr[mid] == target:

return mid

elif arr[mid] < target:

left = mid + 1

else:

right = mid - 1

return -1 # 目标元素不存在

```

3. 时间复杂度

二分法查找的时间复杂度为O(log n)，其中n为有序数组的长度。

4. 注意事项

（1）二分查找只适用于有序数组，因为无序数组的查找时间复杂度是O(n)，效率非常低。

（2）二分查找的前提是数组有序，因此在进行二分查找之前需要先对数组进行排序。

（3）二分查找虽然效率很高，但是需要占用额外的空间，因为需要使用新的变量来存储索引。

三、案例说明

例如，有一个有序数组arr = [1, 3, 5, 7, 9, 11, 13, 15]，现在需要查找元素13，使用二分法查找，其过程如下：

第一次查找：

left = 0，right = 7，mid = (0 + 7) // 2 = 3，arr[mid] = 7 < 13，说明目标元素在mid的右边。

第二次查找：

left = 4，right = 7，mid = (4 + 7) // 2 = 5，arr[mid] = 11 < 13，说明目标元素在mid的右边。

第三次查找：

left = 6，right = 7，mid = (6 + 7) // 2 = 6，arr[mid] = 13 = 13，找到目标元素，返回mid。

因此，使用二分查找可以在3次比较中找到目标元素，时间复杂度为O(log n)。 如果你喜欢我们三七知识分享网站的文章， 欢迎您分享或收藏知识分享网站文章 欢迎您到我们的网站逛逛喔！https://www.37seo.cn/