说明Python中的二进制搜索

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

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

二进制搜索如何工作？

二进制搜索的基本思想是，我们将比较必需元素与数组的中间元素，而不是将所需元素与数组的所有元素进行比较。如果这确实是我们要寻找的元素，则搜索成功。否则，如果我们要查找的元素小于中间元素，则可以确保该元素位于数组的前半部分或左半部分，因为对数组进行了排序。同样，如果我们要查找的元素大于中间元素，则可以确保该元素位于数组的后半部分。

因此，二进制搜索将数组连续缩小为一半。上面的过程将递归应用于数组的选定部分，直到找到所需的元素。

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

我们如何知道数组中是否不存在element？

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

例子

让我们采用以下排序后的数组，我们需要搜索元素6。

L = 0 H = 8中= 4

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

H =中1

L = 0 H = 3中= 1

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

L =中+1

L = 2 H = 3中= 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。