折半查找法之美

注意二分法查找的前提是要已经排行序。

//递归二分法
#include<iostream>
#include<stdio.h>
#include<stdlib.h>

using namespace std;
int a[Max],key;

int Search(int bot,int top)
{
  int mid;
  if(top>=bot)
  {
    mid=(top+bot)/2;
    if(key==a[mid])
     {
       cout<<mid<<endl;
       return 0;
     }
    else if(key>a[mid])
     { 
        Search(mid+1,top);
     }
    else
     {
        Search(bot,mid-1);
     }
  }
 else
  {
      printf("-1\n");
      return 0;
  }
}


int main()
{
  freopen("half.in","r",stdin);
  freopen("half.out,"w",stdout);
  int n;
  cin>>n;
  for(int i=1;i<=n;++i)
    cin>>a[i];
  cin>>key;
  Search(1,n);
  return 0;
}

   
        
//非递归二分法
#include<iostream>
#include<cstdlib>
#define MAXN 10001

using namespace std;

int key,top,bot,mid,n,a[MAXN];

void Half()
{
  top=n;
  bot=1;
  while(bot<=top)
  {
    mid=(bot+top)/2;
    if(key==a[mid])
     {
       cout<<mid<<endl;
       exit(0);
     }
     else if(key>a[mid])
        bot=mid+1;
     else
        top=mid-1;
    }
    cout<<-1<<endl;
}


int main()
{
  freopen("half.in","r",stdin);
  freopen("half.out,"w",stdout);
  cin>>n;
  for(int i=1;i<=n;i++)
    cin>>a[i];
  cin>>key;
  if(key<a[1] || key>a[n])
    cout<<-1<<endl;
  else
    Half();
   return 0;
}

 

上一篇:CIFAR数据集解读


下一篇:盘古量化机器人App系统开发