二分搜索算法(Binary Searc)图文步骤 二分搜索算法实现方式

发布:2022-10-24 15:28:35
阅读:1763
作者:网络整理
分享:复制链接

二分搜索算法(Binary Searc)是一种搜索算法,用于查找元素在已排序数组中的位置。二分搜索只能在已排序的项目列表上实现,如果尚未排序,需要先进行排序。

二分搜索算法的图文步骤

1、初始数组,并定义要搜索的元素X=4

2、在数组的最高、最低值处设置指针

3、找到数组的中间元素,即arr[(low+high)/2]=6

4、如果x==mid,则返回mid。否则,将要搜索的元素与mid进行比较。

5、如果x>mid,比较X与右侧元素的中间元素.这是通过设置完成的low=mid+1。

6、否则,比较X与左侧元素的中间元素.这是通过设置完成的high=mid-1。

7、重复步骤3到6,直到低遇到高。

8、元素x=4被发现。

二分搜索算法可以通过迭代法和递归方法这两种方式实现

迭代法

mid=(low+high)/2
if(x==arr[mid])
return mid
else if(x>arr[mid])//x在右边
low=mid+1
else//x在左侧
high=low-1

递归方法

binarySearch(arr,x,low,high)
if low>high
return False
else
mid=(low+high)/2
if x==arr[mid]
return mid
else if x>arr[mid]//x在右侧
return binarySearch(arr,x,mid+1,high)
else//x在右侧
return binarySearch(arr,x,low,mid-1)
扫码进群
微信群
免费体验AI服务