当前位置：首页 > 资讯 > 技术文档

C++ 先对数组排序,在进行折半查找

时间：2022-05-10 05:58 编辑：来源：阅读：
扫一扫，手机访问

摘要：C++ 先对数组排序,在进行折半查找

第一步：输入15个整数第二步：对这15个数进行排序第三部：输入一个数，在后在排好序的数中进行折半查找，判断该数的位置 [b]实现代码如下：[/b] [b]方法一：[/b] 选择排序法+循环折半查找法

#include<iostream>
using namespace std;
int main(){
 int a[15];
 int n,i;
 void array_sort(int a[], int n);
 int zeban(int a[], int start ,int end,int n);
 cout<<"Please input 15 numbers:"<<endl;
 for(i=0;i<15;i++){
  cin>>a[i];
 }
 cout<<"Sorted order:"<<endl;
 //==============选择排序========
 array_sort(a,15);
 //=======输出排序完成的数组====
    for(i=0;i<15;i++){
  cout<<a[i]<<" ";
  }
 cout<<endl;
 cout<<"please input a number:";
 cin>>n;
 //================折半查找==========
 cout<<endl;
 cout<<"number "<<n<<" locate in "<<zeban(a,0,14,n)<<endl;
 return 0;
}
void array_sort(int a[],int n){
 int i,j,k,tool;
     for(i=0;i<n;i++){
  k=i;
  for(j=(i+1);j<n;j++){
  if(a[j]<a[k]){
     k=j;
        }
  }
  tool=a[i];
  a[i]=a[k];
  a[k]=tool;
  }
}
int zeban(int a[],int start,int end,int n){
 int tag=-1;
 for(start=0,end=14;start<=end;){
  if(n==a[(start+end)/2]){
   tag=(start+end)/2+1;
   return tag;
  }else if(n<a[(start+end)/2]){
   end=(start+end)/2;
  }else if(n>a[(start+end)/2]){
   start=(start+end)/2;
  }
 }
}

[b]第二种方法：[/b] 冒泡排序法+递归折半查找法

[u]复制代码[/u] 代码如下:

#include<iostream>
using namespace std;
int main(){
 int a[15];
 int n,i;
 void array_sort(int a[], int n);
    int IterBiSearch(int data[], const int x, int beg, int last);
 cout<<"Please input 15 numbers:"<<endl;
 for(i=0;i<15;i++){
  cin>>a[i];
 }
 cout<<"Sorted order:"<<endl;
 //==============选择排序========
 array_sort(a,15);
 //=======输出排序完成的数组====
    for(i=0;i<15;i++){
  cout<<a[i]<<" ";
  }
 cout<<endl;
 cout<<"please input a number:";
 cin>>n;
 //================折半查找==========
 cout<<endl;
 cout<<"number "<<n<<" locate in "<<IterBiSearch(a,n, 0, 14)<<endl;
 return 0;
}
void array_sort(int a[],int n){
 int i,j,tool;
     for(i=0;i<n;i++){
     for(j=0;j<(n-i-1);j++){
        if(a[j]>a[j+1]){
           tool=a[j];
           a[j]=a[j+1];
           a[j+1]=tool;
        }
     }
    }
}
int IterBiSearch(int data[], const int x, int beg, int last) 
{ 
    int mid = -1; 
    mid = (beg + last) / 2; 
    if (x == data[mid]) 
    { 
        return (mid+1); 
    } 
    else if (x < data[mid]) 
    { 
        return IterBiSearch(data, x, beg, mid - 1); 
    } 
    else if (x > data[mid]) 
    { 
        return IterBiSearch(data, x, mid + 1, last); 
    } 
    return -1; 
} 

全部评论(0)

上一篇：使用单链表实现多项式计算示例
下一篇：双缓冲解决VC++绘图时屏幕闪烁

资讯排行榜
更多>>