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.

by nikoo28
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.

0 comment

You may also like

Enclose codes in [code lang="JAVA"] [/code] tags

This site uses Akismet to reduce spam. Learn how your comment data is processed.

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