《Cracking the Coding Interview》——第11章：排序和搜索——题目3
2024-09-04 22:10:08
2014-03-21 20:55
题目：给定一个旋转过的升序排序好的数组，不知道旋转了几位。找出其中是否存在某一个值。
解法1：如果数组的元素都不重复，那么我的解法是先找出旋转的偏移量，然后进行带偏移量的二分搜索。两个过程都是对数级的。
代码：
// 11.3 Given a sorted array rotated by a few positions, find out if a value exists in the array.
// Suppose all elements in the array are unique.
#include <algorithm>
#include <vector>
#include <cstdio>
using namespace std; int rotatedBinarySearch(vector<int> &v, int n, int key)
{
int offset; if ((int)v.size() < n || n <= ) {
return -;
} int ll, rr, mm; if (v[] < v[n - ]) {
offset = ;
} else {
ll = ;
rr = n - ;
while (rr - ll > ) {
mm = (ll + rr) / ;
if (v[mm] > v[ll]) {
ll = mm;
} else {
rr = mm;
}
}
offset = rr;
} ll = ;
rr = n - ;
while (ll <= rr) {
mm = (ll + rr) / ;
if (key < v[(mm + offset) % n]) {
rr = mm - ;
} else if (key > v[(mm + offset) % n]) {
ll = mm + ;
} else {
return (mm + offset) % n;
}
}
return -;
} int main()
{
int n;
int i;
vector<int> v; while (scanf("%d", &n) == && n > ) {
v.resize(n);
for (i = ; i < n; ++i) {
scanf("%d", &v[i]);
}
scanf("%d", &i);
printf("%d\n", rotatedBinarySearch(v, n, i));
} return ;
}
解法2：如果数组的元素可能存在重复，那么我的思路仍然是先二分查找找出偏移量，然后执行带偏移量的二分搜索。不过，在找偏移量的过程中可能会出现无法决定向左还是向右的情况，比如这两个例子{1, 3, 1, 1, 1}{1, 1, 1, 3, 1}，在第一次二分时，左中右的元素都是‘1’，无法确定应该往哪边走。这时就得扫描整段，{1, 1, 1}全部是同一元素，{1, 3, 1}存在不同元素，所以应该选择{1, 3, 1}进行二分，因为在首尾相同的情况下，中间如果有不同元素的话，表示旋转的偏移量应该会落在这个区间里。找到偏移量以后，之后的查找就是严格二分的了。
代码：
// 11.3 Given a sorted array rotated by a few positions, find out if a value exists in the array.
// Suppose the array may contain duplicates, what's it gonna be then?
#include <algorithm>
#include <vector>
#include <cstdio>
using namespace std; int rotatedBinarySearch(vector<int> &v, int n, int key)
{
int offset; if ((int)v.size() < n || n <= ) {
return -;
} int ll, rr, mm;
int i; ll = ;
rr = n - ;
while (rr - ll > && v[ll] == v[rr]) {
mm = (ll + rr) / ;
if (v[mm] > v[ll]) {
ll = mm;
break;
} else if (v[mm] < v[ll]) {
rr = mm;
break;
} else {
for (i = ll; i < mm - ; ++i) {
if (v[i] != v[i + ]) {
break;
}
}
if (i < mm - ) {
rr = mm;
break;
}
for (i = mm; i < rr - ; ++i) {
if (v[i] != v[i + ]) {
break;
}
}
if (i < rr - ) {
break;
} // if all elements are the same, it ends here
return (v[] == key) ? : -;
}
} if (v[ll] < v[rr]) {
offset = ;
} else {
// here it is guaranteed v[ll] != v[rr]
while (rr - ll > ) {
mm = (ll + rr) / ;
if (v[mm] >= v[ll]) {
ll = mm;
} else {
rr = mm;
}
}
offset = rr;
} // the binary search part remains the same, difference lies in how we find the 'offset'.
ll = ;
rr = n - ;
while (ll <= rr) {
mm = (ll + rr) / ;
if (key < v[(mm + offset) % n]) {
rr = mm - ;
} else if (key > v[(mm + offset) % n]) {
ll = mm + ;
} else {
return (mm + offset) % n;
}
} return -;
} int main()
{
int n;
int i;
vector<int> v; while (scanf("%d", &n) == && n > ) {
v.resize(n);
for (i = ; i < n; ++i) {
scanf("%d", &v[i]);
}
scanf("%d", &i);
printf("%d\n", rotatedBinarySearch(v, n, i));
} return ;
}
最新文章
- pointer on c
- OC中的内存管理
- 十分钟掌握Activity的生命周期与启动模式
- NBU7.0.1迁移C:\Veritas\Netbackup\db到其他盘
- 使用Jquery+EasyUI 进行框架项目开发案例讲解之二---用户管理源码分享
- [py]安装ipython
- 【转】DBMS_STATS.GATHER_TABLE_STATS详解 2012-04-22 09:20:10
- iOS 8自动调整UITableView和UICollectionView布局
- hdu 1443 Joseph （约瑟夫环）
- sys--system-sysdba-sysoper用户区别
- SQL语言学习-数据定义语言
- linux下Ftp环境的搭建
- Java序列化详解
- 6月6 Smarty练习----设置题目及打印试卷
- springcloud Eureka自我保护机制
- js实例属性和原型属性
- Python封装
- 转载：http://www.cnblogs.com/double-K/p/6926367.html
- 关于 Java连接sql的转载
- java 代码中设置 临时 环境变量