二分法查找算法代码

二分法查找算法，也被称为折半查找算法，是一种在有序数组中查找某一特定元素的搜索算法。它的基本思想是将数组分成两个部分，每次比较中间元素和目标值，如果目标值小于中间元素，则在左半部分继续查找，否则在右半部分查找，直到找到目标值或者搜索范围为空。

二分法查找算法的基本步骤如下：

1.计算数组的中间索引。

2.如果目标值等于中间元素，返回中间元素的索引。

3.如果目标值小于中间元素，则在左半部分（即中间元素的左边）重复上述过程。

4.如果目标值大于中间元素，则在右半部分（即中间元素的右边）重复上述过程。

python

defbinary_search(array,target):

low=0

high=len(array)-1

whilelow<=high:

mid=(low+high)//2

ifarray[mid]==target:

returnmid

elifarray[mid]

low=mid+1

else:

high=mid-1

return-1

在这个代码中，我们首先初始化两个指针，一个指向数组的开始，另一个指向数组的结束。然后我们进入一个循环，直到两个指针相遇或者交叉。在每次循环中，我们计算中间元素的索引，并与目标值进行比较。如果目标值等于中间元素，我们返回中间元素的索引。如果目标值小于中间元素，我们将左指针移动到中间元素的右边。如果目标值大于中间元素，我们将右指针移动到中间元素的左边。如果循环结束时还没有找到目标值，我们返回-1，表示目标值不在数组中。

拓展资料：

1.二分法查找算法的时间复杂度为O(logn)，其中n是数组的长度。这是因为它每次都将搜索范围减半，因此搜索效率非常高。

2.二分法查找算法要求数组必须是有序的，如果数组是无序的，那么就不能使用二分法查找算法。

3.二分法查找算法不仅可以用于查找，还可以用于插入和删除操作。例如，在有序数组中插入一个元素时，我们可以先使用二分法查找算法找到插入位置，然后再进行插入操作。

二分法查找算法是一种非常高效的查找算法，尤其适用于大规模数据的处理。但是，它也有一定的局限性，比如要求数据必须是有序的。因此，在实际应用中，我们需要根据具体情况进行选择。