有序数组倒置后 查找算法

有一个有序数组，比如1，2，3，4，5，6，7

倒置后变成5，6，7，1，2，3，4。

查找一个数，比如1。给出最有算法。

输入：5，6，7，1，2，3，4 查找数 1

输出：3

思路：只要是有序数组第一个想到的是二分法查找。此时的数组被分成最多两个有序数组。

其实，仍然可以使用二分法，因为二分法的效率高是因为在取中间数之后，利用数组的有序性

来裁剪不能存在目标值的区域。而此时，我们使用二分法分割成两个区域后，总会有一个区域是有序的，

所以可以对这个有序区域进行比较边界值，来判断目标值是否存在这个有序区域，如果不存在，那么这个

区域不用查找，提交效率。在不断二分法这个数组，大部分都分成有序的子数组。

#include <iostream> #include <assert.h> using namespace std; #define CHECK_RETURN(x) {int r = x; if( (r) >=0 ) return (r); } int count = 0; // 比较次数 // int find_number( const int* pNums,int start,int end,int num ) { assert(pNums); if( start > end ) return -1; int result = -1; unsigned int mid = (end + start) / 2; if( pNums[mid] == num ) return mid; count ++; // 查找的次数增1 // 下一轮搜索 { if( pNums[mid] <= pNums[end] && pNums[mid] >= pNums[start] ) // 此时为有序数列 { if( pNums[mid] > num && pNums[start] <= num ) // 可能在区域[start,mid-1] CHECK_RETURN(find_number( pNums,start,mid-1,num )) else if( pNums[mid] < num && pNums[end] >= num ) // 可能在区域[mid+1,end] CHECK_RETURN(find_number( pNums,mid+1,end,num )) else return -1; } else // 无序数列 { CHECK_RETURN(find_number(pNums,num)) CHECK_RETURN(find_number(pNums,num)) } } } void main() { int nums[] = {10,10,11,12,13,1,2,3,5,6,7,8,9,10}; int num = 9; int r = find_number(nums,sizeof(nums) / sizeof(int) - 1,num); if( r<0 ) cout <<"not found!"<<endl; else cout << nums[r] << "查找的索引号：" << r << endl; assert(nums[r] == num); cout << "共查找了" << count << "次" << endl; system("pause"); }

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!