*899*

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.