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

时间:2021-12-11 01:17:41

第一步:输入15个整数

第二步:对这15个数进行排序

第三部:输入一个数,在后在排好序的数中进行折半查找,判断该数的位置

实现代码如下:

方法一:

选择排序法+循环折半查找法

复制代码 代码如下:

#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;
  }
 }
}

第二种方法:

 

冒泡排序法+递归折半查找法

复制代码 代码如下:

#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;