Problem
Given a strictly sorted (increasing) array, find an elements whose value is equal to its index i.e. a[i] = i ?
The running time of the solution must be O(logn)
Solution
If an array is strictly sorted, then arr[index] - index is non-decreasing, so binary search can be applied.
/*
============================================================================
Author : James Chen
Email : a.james.chen@gmail.com
Description : Find the elements whose value is equal to their index.
Created Data : 24-06-2013
Last Modified :
============================================================================
*/
#include <iostream>
#include <iomanip>
using namespace std;
int FindElementMatchIndex(int* arr, int len)
{
if(len < 1) return -1;
int low = 0;
int up = len -1;
int mid;
while(low <= up){
mid = (low + up) / 2;
if(arr[mid] - mid == 0){
return mid;
}
else if(arr[mid] - mid > 0){
up = mid - 1;
}
else{
low = mid + 1;
}
}
return -1;
}
void PrintArray(int* arr, int len)
{
for(int i = 0; i < len; ++i){
cout << setw(4) << arr[i];
}
cout << endl;
}
void DoTest(int* arr, int len)
{
cout << "The array is " << endl;
PrintArray(arr, len);
int index = FindElementMatchIndex(arr, len);
if(index != -1){
cout << "The element equal to index is at " << setw(4) << index << endl;
}
else{
cout << "No element is found." << endl;
}
cout << "--------------------" << endl;
}
int main(int argc, char* argv[])
{
int arr[20];
for(int i = 0; i < 20; ++i){
cout << setw(4) << i;
}
cout << endl;
arr[0] = 0;
DoTest(arr, 1);
arr[0] = 1;
DoTest(arr, 1);
for(int j = 0; j < 10; ++j){
arr[j] = j;
}
DoTest(arr, 10);
for(int i = 0; i < 10; ++i){
arr[0] = rand() % 10 - 20;
for(int j = 1; j < 10; ++j){
arr[j] = arr[j-1] + rand() % 10 + 1;
}
DoTest(arr, 10);
}
return 0;
}
Output
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
The array is
0
The element equal to index is at 0
--------------------
The array is
1
No element is found.
--------------------
The array is
0 1 2 3 4 5 6 7 8 9
The element equal to index is at 4
--------------------
The array is
-19 -11 -6 -5 5 10 19 28 31 36
No element is found.
--------------------
The array is
-15 -9 -7 1 3 5 11 14 22 29
The element equal to index is at 5
--------------------
The array is
-19 -14 -11 -7 -4 -1 1 8 17 23
No element is found.
--------------------
The array is
-13 -6 -4 5 15 18 26 36 42 47
No element is found.
--------------------
The array is
-17 -15 -12 -8 -4 1 3 5 9 18
No element is found.
--------------------
The array is
-13 -8 -5 3 11 21 25 27 37 46
The element equal to index is at 3
--------------------
The array is
-14 -8 -7 -4 5 12 13 16 21 30
No element is found.
--------------------
The array is
-14 -8 -7 3 4 5 12 14 18 27
The element equal to index is at 4
--------------------
The array is
-11 -7 -2 3 10 11 18 25 27 36
The element equal to index is at 3
--------------------
The array is
-16 -6 1 5 13 22 31 34 44 46
No element is found.
--------------------
Press any key to continue . . .