Solution
1. Binary search whether there is an element in the array
2. Search left boundary
#include <iostream>
using namespace std;
int FindFirstElem(int* arr, int low, int up, int data)
{
bool found = false;
int mid;
if(arr[low] > data || arr[up] < data){
return -1;
}
while(up >= low){
mid = (low + up) / 2;
if(arr[mid] == data){
found = true;
up = mid;
break;
}
else if(arr[mid] > data){
up = mid - 1;
}
else{
low = mid + 1;
}
}
if(!found){
return -1;
}
while(up > low){
mid = (low + up) / 2;
if(arr[mid] < data){
low = mid + 1;
}
else{
up = mid;
}
}
return arr[mid] < data ? mid + 1: mid;
}
int main(int argc, char* argv[])
{
int arr[] = {2,2,2,3,4,5,5,6,6,8,9};
cout << "The array: " << endl;
int arrLen = sizeof(arr) / sizeof(int);
for(int i = 0; i < arrLen; ++ i){
cout << i << " ";
}
cout << endl;
for(int i = 0; i < arrLen; ++ i){
cout << arr[i] << " ";
}
cout << endl;
int testCase[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int testCaseLen = sizeof(testCase) / sizeof(int);
for(int i = 0; i < testCaseLen; ++ i){
int idx = FindFirstElem(arr, 0, arrLen - 1, testCase[i]);
cout << "Find first " << testCase[i] << " at " << idx << endl;
}
return 0;
}
Output
The array:
0 1 2 3 4 5 6 7 8 9 10
2 2 2 3 4 5 5 6 6 8 9
Find first 1 at -1
Find first 2 at 0
Find first 3 at 3
Find first 4 at 4
Find first 5 at 5
Find first 6 at 7
Find first 7 at -1
Find first 8 at 9
Find first 9 at 10
Find first 10 at -1
Press any key to continue . . .
Problem
Given a sorted array, write a function to search first occurrence of a number in the array. If not found return -1.
Example:
{2,2,2,3,4,5,5,6,6,8,9}
search 6
should return 7.