[图解算法] 二分查找Binary-Search—

 #include"iostream.h"

 int BinarySearch(int a[],int left,int right,const int& x)

 {

     if(left<right)

     {

         int middle = (left+right)/;

         if(x==a[middle]) return middle;

         if(x>a[middle]) return BinarySearch(a,middle+,right,x);

         else return BinarySearch(a,left,middle-,x);

     }

 }

 void main(){

     int n,x,i,a[];

     cout<<"input the length of a[]"<<endl;

     cin>>n;

     cout<<"input array a[]"<<endl;

     for(i=;i<n;i++) cin>>a[i];

     cout<<"input the num u want to find"<<endl;

     cin>>x;

     cout<<BinarySearch(a,,n-,x)+<<endl;

 }

[图解+例子]

前提：有序数组。

一、建立数组

（共10个数）

二、传参

int a[] 数组

int left,int right 当前查找范围限定（left=0;right=n-1；10个数即n=10;left=0;right=9）

const int& x 待查找数值（假如查找27）

三、取中间值middle判断

如果27==7 返回当前middle值(0+9)/2=4

如果27>7查找右半段

if (x>a[middle]) return BinarySearch(a,middle+1,right,x); //设定右半段范围（right值不变middle+1）

如果27<7查找左半段

else return BinarySearch(a,left,middle-1,x);//设定左半段范围（left值不变middle-1）

当前查找右半段即 left=5;right=9

如果27==25 返回当前middle值(5+9)/2=7

……

如此继续递归调用BinarySearch函数

直到middle=(8+9)/2=8时；27==27；return middle

[特例]

如果要找元素在边上的话，如36，那么下一次就是left=9;right=9;自然middle也等于9。

[总结]

子问题：范围内取中值；递归不断缩小确定范围。

巴特西

[图解算法] 二分查找Binary-Search——<递归与分治策略>

最新文章

热门文章