Find first or last occurrence of a given number in a sorted array

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 –
 

Download   Run Code

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 –
 

Download   Run Code

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 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz