首页 > 代码库 > 在左移的递减数组中查找某数 【微软面试100题 第四十八题】
在左移的递减数组中查找某数 【微软面试100题 第四十八题】
题目要求：
一个数组是由一个递减数列左移若干位形成的，比如{4，3,2，1,6,5}是由{6，5,4,3,2,1,}左移两位形成的，在这种数组中查找某个数。
题目分析：
方法1 逐个查找，遍历一遍数组，时间复杂度O(N).
方法2 二分查找，时间复杂度O(logN).具体分析见下图：
代码实现：
#include <iostream>using namespace std;int Helper(int a[],int k,int s,int t);int FindKInArray(int a[],int k,int n);int main(void){ int a[] = {4,3,2,1,6,5}; // int Pos = FindKInArray(a,3,6);// int Pos = FindKInArray(a,6,6); int Pos = FindKInArray(a,7,6); if(Pos==-1) cout << "没有找到" << endl; else cout << "找到，在a[" << Pos << "]中" << endl; return 0;}//如果找到，就返回在数组中的位置,没有找到就返回-1int FindKInArray(int a[],int k,int n){ return Helper(a,k,0,n-1);}int Helper(int a[],int k,int s,int t){ if(s>t) return -1; int mid; mid = s+(t-s)/2; if(a[mid]==k) return mid; if(a[s]>a[mid]) { if(k<=a[s] && k>a[mid]) return Helper(a,k,s,mid-1); else return Helper(a,k,mid+1,t); } else { if(k<a[mid] && k>=a[t]) return Helper(a,k,mid+1,t); else return Helper(a,k,s,mid-1); }}
在左移的递减数组中查找某数 【微软面试100题 第四十八题】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。