二分查找的扩展有关问题，循环数组中查找某一数字

二分查找的扩展问题，循环数组中查找某一数字

问题：对已排好序的数组A，一般来说可用二分查找可以很快找到。现有一特殊数组A[]，它是循环递增的，如A[]={ 17 19 20 25 1 4 7 9}，试在这样的数组中找一元素x，看看是否存在。请写出你的算法，必要时可写伪代码，并分析其空间、时间复杂度。

思路：首先可先确定循环数组最大元素的位置，例如，给定的例子当中最大元素为25，下标为3，确定了最大元素的位置之后，可以根据要查找的元素与A[0]的大小关系来确定在数组的哪一部分查找，确定最大元素位置的过程本身也二分查找的一个扩展问题，思想比较简单，一下给出实现代码，相信大家都能轻松理解。

#include<iostream>
using namespace std;
int bin_search(int *data,int len,int key);
int main()
{
	int len;
	cin>>len;//输入数组data的长度len
	int *data=new int[len];
	for(int i=0;i<len;i++)//输入数组data的元素值
		cin>>data[i];
	int key;
	cin>>key;//输入要查找的数字
	int index=bin_search(data,len,key);
	if(index==-1)
		cout<<"Can not find "<<key<<endl;
	else
		cout<<"data["<<index<<"]="<<key<<endl;
	delete []data;
	return 0;
}
int bin_search(int *data,int len,int key)
{
	if(data==NULL||len<=0)
		return -1;
	int start,mid,end;
	start=0;
	end=len-1;
	mid=end;
	while(data[start]>=data[end])
	{
		if(end-start==1)//找到了循环数组中最大的元素的位置start
		{
			mid=start;
			break;
		}
		mid=start+(end-start)/2;
		if(data[mid]==data[start]&&data[mid]==data[end])//mid,start,end三个下标对应的元素相等，只通过线性遍历确定最大元素的位置
		{
			for(int i=start;i<=end;i++)
			{
				if(data[i]>data[i+1])
					mid=i;
			}
			break;
		}
		else if(data[start]<=data[mid])
			start=mid;
		else
			end=mid;
	}
	if(key==data[0])
		return 0;
	else if(key<data[0])
	{
		start=mid+1;
		end=len-1;
		int index;
		while(start<=end)
		{
			index=start+(end-start)/2;
			if(data[index]==key)
				return index;
			else if(data[index]>key)
				end=index-1;
			else
				start=index+1;
		}
		return -1;
	}
	else
	{
		start=0;
		end=mid;
		int index;
		while(start<=end)
		{
			index=start+(end-start)/2;
			if(data[index]==key)
				return index;
			else if(data[index]>key)
				end=index-1;
			else
				start=index+1;
		}
		return -1;
	}
}

时间复杂度为O(logn),空间复杂度为O(1).

1楼jirongzi_cs20113小时前: 此问题其实还有个更为直接的方法，不用先确定最大元素的位置，而是根据key,data[start],data[end],data[mid]四者的大小关系来确定在数组的哪一部分进行搜索，大家可以自己实现

二分查找的扩展有关问题，循环数组中查找某一数字

相关推荐