Given a sorted array of integers, find index of first or last occurrence of a given number. If the element is not found in the array, report that as well.

For example,

**Input: **

arr = [2, 5, 5, 5, 6, 6, 8, 9, 9, 9]

target = 5

**Output: **

First occurrence of element 5 is found at index 1

Last occurrence of element 5 is found at index 3

**Input: **

arr = [2, 5, 5, 5, 6, 6, 8, 9, 9, 9]

target = 4

**Output: **

Element not found in the array

A simple solution would be to run a linear seach on the array and return first or last occurrence of the given element. The problem with this approach is that its worst case time complexity is O(n). This solution also do not take advantage of the fact that the input is sorted. We can easily solve this problem in O(log(n)) time. The idea is to modify the binary search algorithm to solve this problem.

#### Finding first occurrence of the element

In normal binary search, we return as soon as we find any occurrence of the given target element in it. In order to find the first occurrence of the element, the idea is to modify the normal binary search in such a way that we do not stop the search as soon we find any occurrence of the target element. Instead we update the result to mid and go on searching towards left (towards lower indices) i.e. modify our search space by adjusting high to mid – 1 on finding the target at mid index.

**C++ implementation –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 |
#include <iostream> using namespace std; // Function to find first occurrence of a given number // in sorted array of integers int findFirstOccurrence(int A[], int N, int x) { // search space is A[low..high] int low = 0, high = N - 1; // initialize the result by -1 int result = -1; // iterate till search space contains at-least one element while (low <= high) { // find the mid value in the search space and // compares it with target value int mid = (low + high)/2; // if target is found, update the result and // go on searching towards left (lower indices) if (x == A[mid]) { result = mid; high = mid - 1; } // if target is less than the mid element, discard right half else if (x < A[mid]) high = mid - 1; // if target is more than the mid element, discard left half else low = mid + 1; } // return the leftmost index or -1 if the element is not found return result; } // main function int main() { int A[] = {2, 5, 5, 5, 6, 6, 8, 9, 9, 9}; int n = sizeof(A)/sizeof(A[0]); int target = 5; int index = findFirstOccurrence(A, n, target); if (index != -1) cout << "First occurrence of element " << target << " is found at index " << index; else cout << "Element not found in the array"; return 0; } |

**Output: **

First occurrence of element 5 is found at index 1

#### Finding last occurrence of the element

In order to find the last occurrence of the element, the idea is to modify the normal binary search in such a way that we do not stop the search as soon we find any occurrence of the target element. Instead we update the result to mid and go on searching towards right (towards higher indices) i.e. modify our search space by adjusting low to mid + 1 on finding the target at mid index.

**C++ implementation –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 |
#include <iostream> using namespace std; // Function to find last occurrence of a given number // in sorted array of integers int findLastOccurrence(int A[], int N, int x) { // search space is A[low..high] int low = 0, high = N - 1; // initialize the result by -1 int result = -1; // iterate till search space contains at-least one element while (low <= high) { // find the mid value in the search space and // compares it with target value int mid = (low + high)/2; // if target is found, update the result and // go on searching towards right (higher indices) if (x == A[mid]) { result = mid; low = mid + 1; } // if target is less than the mid element, discard right half else if (x < A[mid]) high = mid - 1; // if target is more than the mid element, discard left half else low = mid + 1; } // return the leftmost index or -1 if the element is not found return result; } // main function int main() { int A[] = {2, 5, 5, 5, 6, 6, 8, 9, 9, 9}; int n = sizeof(A)/sizeof(A[0]); int target = 5; int index = findLastOccurrence(A, n, target); if (index != -1) cout << "First occurrence of element " << target << " is found at index " << index; else cout << "Element not found in the array"; return 0; } |

**Output: **

Last occurrence of element 5 is found at index 3

**Time complexity** of above solutions is O(log(n)).

**Auxiliary space** used by the program is O(1).

**Exercise:**

1. Write recursive versions of above solution

2. Check if given integer appears more than n/2 times in a sorted array

**References:**

**Thanks for reading.**

Please use ideone or C++ Shell or any other online compiler link to post code in comments.

Like us? Please spread the word and help us grow. Happy coding 🙂