Home Arrays Find the index of last occurrence of an element in a sorted array.

# Find the index of last occurrence of an element in a sorted array.

0 comment

Question: Given a sorted array A of n elements, possibly with duplicates, find the index of the last occurrence of a number in O(log n) time.

Input: 4, 4, 8, 8, 8, 15, 16, 23, 23, 42. Find 8
Output: Index = 4 (0 based indexing)

This problem is very much similar to the binary search problem. We can apply the same methodology with just an added condition. For a number to be the last occurrence in the array, the number to the right of it must be larger. We just add this condition to our loop.

if((mid == high && arr[mid] == data) || (arr[mid] == data && arr[mid+1] > data))


Here is the sample code for the same:-

#include<stdio.h>

int binarySearchLastOccurrence(int arr[], int low, int high, int data)
{
int mid;

// A simple implementation of Binary Search
if(high >= low)
{
mid = low + (high - low)/2;	// To avoid overflow
if((mid == high && arr[mid] == data) || (arr[mid] == data && arr[mid+1] > data))
return mid;

// We need to give preference to right part of the array
// since we are concerned with the last occurrence
else if(arr[mid] <= data)
return binarySearchLastOccurrence(arr, mid+1, high, data);
else
// We need to search in the left half
return binarySearchLastOccurrence(arr, low, mid-1, data);
}
}

int getLastOccurrence(int arr, int len, int data)
{
int low = 0;
int high = len - 1;

int index = binarySearchLastOccurrence(arr, low, high, data);

return index;
}

// Driver program to test the code
int main(void)
{
int arr[] = {4, 4, 8, 8, 8, 15, 15, 16, 23, 42, 42};

int result = getLastOccurrence(arr, 11, 8);

printf("The last occurrence is at = %d", result);

return 0;
}


Time Complexity:- O(log n)
Space Complexity:- O(1)

This problem is almost similar to finding the first occurrence.

#### You may also like

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More