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>
#include <time.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>
using namespace std;
void rotate_shift_right_one(int a[], int len)
{
int t = a[len - 1];
for(int i = len - 2; i >= 0; i --){
a[i + 1] = a[i];
}
a[0] = t;
}
void rotate_array(int a[], int len, int pos)
{
for(int i = 0; i < pos; i ++){
rotate_shift_right_one(a, len);
}
}
void print_array(int a[], int len)
{
for(int i = 0; i < len; i ++){
cout << a[i] << " ";
}
cout << endl;
}
int find_in_order(int a[], int l, int u, int x)
{
if(x < a[l] || x > a[u]){
return -1;
}
while(l <= u){
int m = (l + u) / 2;
if(a[m] == x){
return m;
}
else if(a[m] > x){
u = m - 1;
}
else{
l = m + 1;
}
}
return -1;
}
void find_elem(bool &found, int &pos, int a[], int low, int up, int x)
{
if(found){
return ;
}
if(low > up){
return ;
}
if(a[low] <= a[up]){ // in order
pos = find_in_order(a, low, up, x);
if(pos != -1){
found = true;
return;
}
}
else{ // has been rotated
int m = (low + up) / 2;
if(a[m] == x){
found = true;
pos = m;
return;
}
else{
if(a[m] >= a[low]){
pos = find_in_order(a, low, m - 1, x); // low half
if(pos == -1){
find_elem(found, pos, a, m + 1, up, x);
}
else{
found = true;
return;
}
}
else{
pos = find_in_order(a, m + 1, up, x); // up half
if(pos == -1){
find_elem(found, pos, a, low, m - 1, x);
}
else{
found = true;
return;
}
}
}
}
}
int main(int argc, char* argv[])
{
srand((unsigned)time(NULL));
int a[15];
int n = rand() % 15;
vector<int> v;
for(int i = 0; i < 15; i ++){
v.push_back(rand()%20);
}
sort(v.begin(), v.end());
for(int j = 0; j < 15; j += 5){
for(int i = 0; i < 15; i ++){
a[i] = i * 2;
}
rotate_array(a, 15, j);
cout << "before " << endl;
print_array(a, 15);
for(int k = -2; k < 40; k += 3){
cout << "find " << k << " -- pos: ";
bool found = false;
int pos = -1;
find_elem(found, pos, a, 0, 14, k);
cout << pos << endl;
}
}
return 0;
}
Output
before
0 2 4 6 8 10 12 14 16 18 20 22 24 26 28
find -2 -- pos: -1
find 1 -- pos: -1
find 4 -- pos: 2
find 7 -- pos: -1
find 10 -- pos: 5
find 13 -- pos: -1
find 16 -- pos: 8
find 19 -- pos: -1
find 22 -- pos: 11
find 25 -- pos: -1
find 28 -- pos: 14
find 31 -- pos: -1
find 34 -- pos: -1
find 37 -- pos: -1
before
20 22 24 26 28 0 2 4 6 8 10 12 14 16 18
find -2 -- pos: -1
find 1 -- pos: -1
find 4 -- pos: 7
find 7 -- pos: -1
find 10 -- pos: 10
find 13 -- pos: -1
find 16 -- pos: 13
find 19 -- pos: -1
find 22 -- pos: 1
find 25 -- pos: -1
find 28 -- pos: 4
find 31 -- pos: -1
find 34 -- pos: -1
find 37 -- pos: -1
before
10 12 14 16 18 20 22 24 26 28 0 2 4 6 8
find -2 -- pos: -1
find 1 -- pos: -1
find 4 -- pos: 12
find 7 -- pos: -1
find 10 -- pos: 0
find 13 -- pos: -1
find 16 -- pos: 3
find 19 -- pos: -1
find 22 -- pos: 6
find 25 -- pos: -1
find 28 -- pos: 9
find 31 -- pos: -1
find 34 -- pos: -1
find 37 -- pos: -1