C++ 数组排序与折半查找算法实现

逻辑流程与运行结果

程序的执行遵循严格的线性步骤：

1. 输入数据：读取 15 个整数存入数组。
2. 执行排序：调用排序函数对数组进行升序排列。
3. 输出验证：打印排序后的数组以确认数据有序。
4. 输入查找值：用户输入需要定位的数字。
5. 计算并返回位置：程序输出该数字在数组中的索引（从 1 开始计数的位置），若不存在则返回特定标记。

方法一：选择排序 + 迭代折半查找

第1步：主逻辑与排序实现

程序首先声明包含 15 个整数的数组 a。随后调用 array_sort 函数。该方法采用选择排序（Selection Sort）：遍历未排序部分寻找最小值，并将其与当前位置交换。

第2步：迭代折半查找函数

zeban 函数利用 while 循环不断缩小查找范围。它比较目标值与当前中间元素的值：

• 若相等，返回计算出的中间位置。
• 若目标值较小，更新右边界为 (start+end)/2。
• 若目标值较大，更新左边界为 (start+end)/2。

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

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

第1步：主逻辑与冒泡排序实现

此版本同样输入 15 个数并输出排序结果，但排序算法换为冒泡排序（Bubble Sort）。它通过相邻元素的比较和互换，逐步将最大值“冒泡”到数组末尾。

第2步：递归折半查找函数

IterBiSearch 函数通过自身调用来处理子区间。每次计算中间点 mid，匹配则返回；不匹配则根据大小关系，向左或向右发起新的递归调用，直到找到目标或范围失效。

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

关键点说明

在实际应用中，折半查找的前提是数据已按升序或降序排列。上述代码中：
1. selection_sort 的时间复杂度为 O(n²)。
2. bubble_sort 同样为 O(n²)，但在大数据量下性能较差。
3. 两种折半查找的效率均为 O(log n)。

以上就是 C++ 数组排序与折半查找的详细教程，更多关于 C++ 基础算法的资料请关注本站其它相关文章！