Python中的二分查找详解

二分查找是一种用于在已排序数组中搜索元素的搜索算法。它不能用于在未排序数组中搜索。二分查找是一种高效的算法，在时间复杂度方面优于线性查找。

线性查找的时间复杂度为O(n)。而二分查找的时间复杂度为O(log n)。因此，二分查找是一种高效且快速的搜索算法，但只能用于在已排序数组中搜索。

二分查找是如何工作的？

二分查找的基本思想是，与其将所需元素与数组的所有元素进行比较，不如将其与数组的中间元素进行比较。如果这恰好是我们正在寻找的元素，那么搜索就成功完成了。否则，如果我们正在寻找的元素小于中间元素，则可以确定该元素位于数组的前半部分或左半部分（因为数组已排序）。类似地，如果我们正在寻找的元素大于中间元素，则可以确定该元素位于数组的后半部分。

因此，二分查找不断将数组减半。上述过程递归地应用于所选数组的一半，直到找到我们正在寻找的元素。

我们将从左索引0和右索引（等于数组的最后一个索引）开始搜索。计算中间元素索引(mid)，它是左索引和右索引之和除以2。如果所需元素小于中间元素，则右索引更改为mid-1，这意味着我们现在只关注数组的前半部分。同样，如果所需元素大于中间元素，则左索引更改为mid+1，这意味着我们现在只关注数组的后半部分。我们将对所选数组的一半重复上述过程。

我们如何知道元素不存在于数组中？

我们需要一些条件来停止进一步的搜索，这将表明该元素不存在于数组中。只要左索引小于或等于右索引，我们就将迭代地搜索数组中的元素。一旦此条件变为false，而我们尚未找到该元素，则表示该元素不存在于数组中。

示例

让我们取以下已排序数组，我们需要搜索元素6。

L=0 H=8 Mid=4

6<10，因此取前半部分。

H=Mid-1

L=0 H=3 Mid=1

6>5，因此选择后半部分。

L=Mid+1

L=2 H=3 Mid=2

6==6，找到元素

因此，元素6位于索引2处。

实现

从给定的已排序数组中，搜索所需的元素，如果该元素存在于数组中，则打印其索引。如果元素不存在，则打印-1。

下面给出二分查找实现的代码。

示例

 在线演示

def binary_search(arr,x):
   l=0
   r=len(arr)-1
   while(l<=r):
      mid=(l+r)//2
      if(arr[mid]==x):
         return mid
      elif(x<arr[mid]):
         r=mid-1
      elif(x>arr[mid]):
         l=mid+1
   return -1
array=[1,2,3,4,5,6,7,8,9,10]
a=7
print(binary_search(array,a))
b=15
print(binary_search(array,b))

输出

6
-1

元素7位于索引6处。

数组中不存在元素15，因此打印-1。

pawandeep

更新于：2021年3月11日

4K+ 次浏览

启动您的职业生涯

完成课程后获得认证

开始学习