Problem
Given a sorted integer array and a number, find the start and end indexes of the number in the array.
Ex1: Array = {0,0,2,3,3,3,3,4,7,7,9} and Number = 3 --> Output = {3,6}
Ex2: Array = {0,0,2,3,3,3,3,4,7,7,9} and Number = 5 --> Output = {-1,-1}
Complexity should be less than O(n)
Solution
/*
============================================================================
Author : James Chen
Email : a.james.chen@gmail.com
Description : Find the start and end indexes of the number in the array
Created Date : 13-July-2013
Last Modified :
===========================================================================
*/
#include <iostream>
#include <iomanip>
#include <cassert>
using namespace std;
int BinarySearch(int* arr, int low, int up, int num)
{
if(arr[low] > num || arr[up] < num) return -1;
while(low <= up){
int mid = low + (up - low) / 2;
if(arr[mid] == num) return mid;
else if(arr[mid] > num) up = mid -1;
else low = mid + 1;
}
return -1;
}
void PrintStartEnd(int* arr, int len, int num)
{
int index = BinarySearch(arr, 0, len -1, num);
if(index == -1){
cout << "[-1, -1]" << endl;
return;
}
int start_up = index - 1;
int end_low = index + 1;
while((start_up >= 0) && (index = BinarySearch(arr, 0, start_up, num)) != -1){
start_up = index -1;
}
while((end_low < len) && (index = BinarySearch(arr, end_low, len - 1, num)) != -1){
end_low = index + 1;
}
cout << "[" << start_up + 1 << ", " ;
cout << end_low - 1 << "]" << endl;
}
void DoTest(int* arr, int len, int num)
{
assert(arr != NULL);
assert(len > 0);
for(int i = 0; i < 20; ++i){
cout << setw(4) << i;
}
cout << "\nThe array is " << endl;
for(int i = 0; i < len; ++i){
cout << setw(4) << arr[i];
}
cout << endl;
cout << "The number to find is " << num << endl;
PrintStartEnd(arr, len, num);
cout << "----------------------------------"<< endl;
}
int main(int argc, char* argv[])
{
int arr0[] = {0,0,2,3,3,3,3,4,7,7,9};
DoTest(arr0, sizeof(arr0) / sizeof(arr0[0]), 3);
DoTest(arr0, sizeof(arr0) / sizeof(arr0[0]), 5);
int arr[] = {1};
DoTest(arr, sizeof(arr) / sizeof(arr[0]), 0);
DoTest(arr, sizeof(arr) / sizeof(arr[0]), 1);
int arr1[] = {1, 3};
DoTest(arr1, sizeof(arr1) / sizeof(arr1[0]), 0);
DoTest(arr1, sizeof(arr1) / sizeof(arr1[0]), 1);
DoTest(arr1, sizeof(arr1) / sizeof(arr1[0]), 3);
DoTest(arr1, sizeof(arr1) / sizeof(arr1[0]), 4);
int arr2[] = {1, 1};
DoTest(arr2, sizeof(arr2) / sizeof(arr2[0]), -1);
DoTest(arr2, sizeof(arr2) / sizeof(arr2[0]), 0);
DoTest(arr2, sizeof(arr2) / sizeof(arr2[0]), 1);
DoTest(arr2, sizeof(arr2) / sizeof(arr2[0]), 2);
int arr3[] = {1, 3, 5};
DoTest(arr3, sizeof(arr3) / sizeof(arr3[0]), -2);
DoTest(arr3, sizeof(arr3) / sizeof(arr3[0]), 1);
DoTest(arr3, sizeof(arr3) / sizeof(arr3[0]), 3);
DoTest(arr3, sizeof(arr3) / sizeof(arr3[0]), 5);
DoTest(arr3, sizeof(arr3) / sizeof(arr3[0]), 7);
int arr4[] = {1, 1, 1, 2, 3, 5, 7, 7 , 8, 9, 9, 9, 9};
DoTest(arr4, sizeof(arr4) / sizeof(arr4[0]), -1);
DoTest(arr4, sizeof(arr4) / sizeof(arr4[0]), 1);
DoTest(arr4, sizeof(arr4) / sizeof(arr4[0]), 2);
DoTest(arr4, sizeof(arr4) / sizeof(arr4[0]), 7);
DoTest(arr4, sizeof(arr4) / sizeof(arr4[0]), 9);
DoTest(arr4, sizeof(arr4) / sizeof(arr4[0]), 19);
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 0 2 3 3 3 3 4 7 7 9
The number to find is 3
[3, 6]
----------------------------------
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
The array is
0 0 2 3 3 3 3 4 7 7 9
The number to find is 5
[-1, -1]
----------------------------------
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
The array is
1
The number to find is 0
[-1, -1]
----------------------------------
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
The array is
1
The number to find is 1
[0, 0]
----------------------------------
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
The array is
1 3
The number to find is 0
[-1, -1]
----------------------------------
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
The array is
1 3
The number to find is 1
[0, 0]
----------------------------------
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
The array is
1 3
The number to find is 3
[1, 1]
----------------------------------
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
The array is
1 3
The number to find is 4
[-1, -1]
----------------------------------
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
The array is
1 1
The number to find is -1
[-1, -1]
----------------------------------
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
The array is
1 1
The number to find is 0
[-1, -1]
----------------------------------
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
The array is
1 1
The number to find is 1
[0, 1]
----------------------------------
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
The array is
1 1
The number to find is 2
[-1, -1]
----------------------------------
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
The array is
1 3 5
The number to find is -2
[-1, -1]
----------------------------------
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
The array is
1 3 5
The number to find is 1
[0, 0]
----------------------------------
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
The array is
1 3 5
The number to find is 3
[1, 1]
----------------------------------
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
The array is
1 3 5
The number to find is 5
[2, 2]
----------------------------------
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
The array is
1 3 5
The number to find is 7
[-1, -1]
----------------------------------
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
The array is
1 1 1 2 3 5 7 7 8 9 9 9 9
The number to find is -1
[-1, -1]
----------------------------------
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
The array is
1 1 1 2 3 5 7 7 8 9 9 9 9
The number to find is 1
[0, 2]
----------------------------------
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
The array is
1 1 1 2 3 5 7 7 8 9 9 9 9
The number to find is 2
[3, 3]
----------------------------------
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
The array is
1 1 1 2 3 5 7 7 8 9 9 9 9
The number to find is 7
[6, 7]
----------------------------------
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
The array is
1 1 1 2 3 5 7 7 8 9 9 9 9
The number to find is 9
[9, 12]
----------------------------------
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
The array is
1 1 1 2 3 5 7 7 8 9 9 9 9
The number to find is 19
[-1, -1]
----------------------------------
Press any key to continue . . .