Cracking The Coding Interview 9.3
2024-10-15 12:47:52
//Given a sorted array of n integers that has been rotated an unknown number of times, give an O(log n) algorithm that finds an element in the array. You may assume that the array was originally sorted in increasing order.
//
//EXAMPLE:
//
//Input: find 5 in array (15 16 19 20 25 1 3 4 5 7 10 14)
//
//Output: 8 (the index of 5 in the array)
#include <iostream>
using namespace std; //原始二分法
//int search(int *a, int begin, int end,int key)
//{
//int mid;
//while(begin < end)
//{
// mid = (begin + end)/2;
// if (a[mid] == key)
// {
// return mid;
// }
// if (key < a[mid])
// {
// end = mid;
// }
// else
// {
// begin = mid;
// }
//} //if (begin < end)
//{
// int mid = (begin + end)/2;
// if (a[mid] == key)
// {
// return mid;
// }
// if (key < a[mid])
// {
// search(a,begin,mid-1,key);
// }
// else
// {
// search(a,mid+1,end,key);
// }
//}
//} int searchInRotate(int *a, int begin, int end,int key)
{ while(begin < end)
{
int mid = (begin + end)/2;
if (a[mid] == key)
{
return mid;
} if (a[mid] >= a[begin])
{
if (key < a[mid] && key >= a[begin])
{
end = mid-1;
}
else
{
begin = mid+1;
}
}
else
{
if (key > a[mid] && key <a[begin])
{
begin = mid + 1;
}
else
{
end = mid -1;
}
} }
} int main()
{
int a[12] = {15,16,19,20,25,1,3,4,5,7,10,14};
//int a[12] = {1,3,4,5,7,10,14,15,16,19,20,25};
//cout<<search(a,0,11,7);
cout<<searchInRotate(a,0,11,25);
return 0;
}
最新文章
- Docker for Windows使用简介
- yii2实战教程之新手入门指南-简单博客管理系统
- Andriod学习笔记4：mac下搭建 Eclipse+CDT 集成开发环境
- Socket
- 大漠绑定测试工具-VB6
- 国际化支持(I18N)
- Mysql查找所有项目开始时间比之前项目结束时间小的项目ID
- Spring MVC设计模式
- C++ 提取字符串中的数字
- coursera-miniproject stopwatch任务总结
- Java语言基础（四）
- CouchBase 遇到问题笔记（一）
- PHP安全编程：网站安全设计的一些原则(转)
- Activity切换动画---点击哪里从哪放大
- 对于SQL注入的理解
- eclipse哪个版本好
- c# 一些细节
- jQuery中的end()方法
- Windows系统崩溃后快速恢复Oracle数据库的妙招
- [ADC]TI am4378 ADC采样设置问题(am335x类似)