Finding the right most occurence of an element in a sorted array

Given an array of sorted numbers, we have to find the right most occurrence of a number.

For example given an array {1,2,2,2,3}, the right most occurrence of 2 is at index 3 (0-based index).

This post is related to one of my previous posts ( Finding the left most occurrence in sorted array).

Similar to the above problem, we have to utilize binary search to solve this problem in O( log n ) time. Normal binary search returns any index which matches the given value. So, We have to customize binary search to find the right most instance.

In this modified approach, we have to check if we have already reached the end of the array or the middle is different from it’s next element. If it’s different, we return; otherwise we continue with right half of the array.

This function is similar C++ library implementation of upper_bound().

Here is the implementation in C++ which covers various test cases.

	#include <iostream>
	#include <cassert>

	using namespace std;

	int rightmost(int A[], int len, int val)
	{
	if( len <= 0)
	return -1;
	int l = 0;
	int h = len - 1;

	while ( l <= h )
	{
	int m = l + (h-l)/2;

	if( A[m] == val )
	{
	if( m == len-1 \|\| A[m] != A[m+1] )
	return m;
	else
	l = m+1;
	}
	else if( A[m] > val )
	{
	h = m-1;
	}
	else
	{
	l = m+1;
	}
	}
	return -1;
	}
	void TestCase1()
	{
	int A[] = {1};
	assert( rightmost(A,1,1) == 0 );
	}
	void TestCase2()
	{
	int A[] = {0};
	assert( rightmost(A,1,0) == 0 );
	}
	void TestCase3()
	{
	int A[] = {1,2,3};
	assert( rightmost(A,3,2) == 1 );
	}

	void TestCase4()
	{
	int A[] = {1,2,3,4};
	assert( rightmost(A,4,4) == 3 );
	}

	void TestCase5()
	{
	int A[] = {1,2,2,2,3};
	assert( rightmost(A,5,2) == 3 );
	}
	void TestCase6()
	{
	int A[] = {1,2,2,2,3};
	assert( rightmost(A,5,6) == -1 );
	}
	int main()
	{
	TestCase1();
	TestCase2();
	TestCase3();
	TestCase4();
	TestCase5();
	TestCase6();
	return 0;
	}

view raw UpperBound.cpp hosted with

by GitHub

Leave a Reply Cancel reply