VB.net 2010 视频教程 VB.net 2010 视频教程 python基础视频教程
SQL Server 2008 视频教程 c#入门经典教程 Visual Basic从门到精通视频教程
当前位置:
首页 > temp > python入门教程 >
  • Python 有序数列二分查找法

#二分查找法:

二分搜索是一种在有序数组中查找某一特定元素的搜索算法。

搜索过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束;

如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。

如果在某一步骤数组为空,则代表找不到。

这种搜索算法每一次比较都使搜索范围缩小一半。

方法一:(while循环法)

def binarySearch(arr,x): #自定义函数:arr:有序数组;x:待查找值
  low,high=0,len(arr)-1  #初始查询下标索引
  while low<=high: #循环判断
    mid=int((low+high)/2) #获取有序数组中间值下标索引
    if x==arr[mid]: #判断待查找值与中间索引值相同
      return mid #返回索引下标
    elif x>arr[mid]: #判断待查值大于中间索引值时
      low=mid+1 #开始索引下标赋新值
    else: #判断待查值小于中间索引值时
      high=mid-1 #结束索引下标赋新值
  return -1 #while循环判断不成立时

 

#测试
arr=[2,3,4,10,40]
x=10
result=binarySearch2(arr,x)
print(result)

 

方法二:(递归法)

def binarySearch(arr,s,e,x): #自定义递归函数 arr:有序数组,s:开始索引下标,e:结束索引下标,x:待查值
  if s<=e: #循环判断
    mid=int((e+s)/2)  #获取有序数组中间值下标索引
    if arr[mid]==x:  #判断待查找值与中间索引值相同
      return mid  #返回索引下标
    elif arr[mid] < x: #判断待查值大于中间索引值时
      return binarySearch(arr,mid+1,e,x) #递归:开始索引下标赋新值
    else: #判断待查值小于中间索引值时
      return binarySearch(arr,s,mid-1,x) #递归:结束索引下标赋新值
  else: #外层 if 循环判断不成立时
    return -1

 


#测试数组
arr=[2,3,4,10,40]
x=10

#函数调用
result=binarySearch(arr,0,len(arr)-1,x)

print(result)

来源:https://www.cnblogs.com/xiangers/p/15428852.html


相关教程