【模板】有序表的查找（折半查找、循环数组最小元素查找）

最新推荐文章于 2022-03-19 00:04:35 发布

coderwait

最新推荐文章于 2022-03-19 00:04:35 发布

阅读量332

点赞数

分类专栏：算法理论和模板

本文链接：https://blog.csdn.net/coderwait/article/details/89335125

版权

算法理论和模板专栏收录该内容

31 篇文章

订阅专栏

本文介绍两种高效的查找算法：折半查找和循环数组最小元素查找。折半查找利用二分法缩小查找范围，适用于有序数组，时间复杂度为O(log n)。循环数组最小元素查找同样采用二分法，适用于旋转有序数组，时间复杂度也为O(log n)。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

折半查找

原理：是一种二分查找方法。首先确定待查元素的范围，然后不断缩小区间，直到查找成功或者失败。

注意：折半查找判定树。

时间复杂度： $o(log n)$

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#define N 1000
using namespace std;
int searchTime=0; 
int findElem(int a[],int key){
	int low = 0;
	int high = N-1;
	while(low<=high){
		searchTime++;
		int mid = (low+high)/2;
		if(key==a[mid]){
			return mid;
		} 
		else if(key<a[mid]){
			high=mid-1;
		} 
		else{
			low=mid+1;
		}
	}
	return -1;//查找不到 
}
int main(void)
{
	int arr[N];
	for(int i=0;i<N;i++){
		int temp = rand()%N; 
		arr[i]= temp;
	}
	sort(arr,arr+N);//形成有序序列 
	int ans = findElem(arr,arr[789]);
	printf("%d\n%d",ans,searchTime);
	return 0; 
 }

循环数组最小元素的查找

原理：

也是一种二分查找方法。通过判断a[mid]和a[low]或者a[high]的关系，确定最小值在左区间还是右区间，直到成功。

1.当a[low]<a[high]，已经完全有序，a[low]即为最小值。

2.否则，如果a[low]<a[mid]，说明左区间已经有序，最小值在右区间，反之，右区间已经有序，最小值在左区间。

时间复杂度： $o(log n)$

//循环数组寻找最小值 
#include<iostream>
#include<cstring>
using namespace std;
int CycleMin(int a[],int n)//返回循环数组最小元素的下标 
{
	int low = 0; int high = n-1;
	while(low<high)
	{
		int mid = (low+high)/2;
		if(a[low]<=a[high]) return low;	//当前元素已经递增了 
		else if(a[low]<a[mid]) low=mid+1;	//左边递增了，最小元素出现在区间的右边 
		else if(a[mid]<a[high]) high = mid;	// 右边递增了，最小元素出现在区间的左边
	}
	return low; 
}
int main(void){
	int a[]={5,7,9,12,-1,0,1,3,4};
	int ans = CycleMin(a,7);
	printf("%d",ans);
	return 0;
}