Problem

Given a sorted array and an element, find last occurrence of element in array. 

Examples

Example 1:

1
2

Input: a = [1, 4, 4, 10, 10, 15, 20], target = 10
Output: 4

This problem is similar to Find first position of target element in sorted array.

Solution

A brute force solution involves scanning the entire array and comparing each A[index] with the key. If A[index] is equal to the key and the next element is different, return the index. The worst-case time complexity of this method is ( O(N) ). Can we improve this? And the answer is yes, using Binary Search on Sorted Array.

Method 1 - Binary Search

If target == a[mid], update lastPosition to mid. However, to find the very last occurrence of the target, continue checking the right part of the array to see if the target appears at a higher position.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

public int binarySearchLastPosition(int[] a, int target) {
	int start = 0;
	int end = a.length-1;

	int lastPosition = -1;
	while(start <= end) {
		int mid = (start + end)/2;

		if(target == a[mid]) {
			// Found target, update lastPosition and move to the right to find a higher position by setting start=mid+1
			lastPosition = mid;
			start = mid+1;
		} else if (target < a[mid]) {
			end = mid-1;
		} else {
			start = mid+1;
		}
	}

	return lastPosition;
}