First Occurrence And Last Occurrence Functions In C++

Filed Under: C++
First Occurrence And Last Occurrence Functions In C

In this article, we will learn about the concept behind the first occurrence and last occurrence functions in C++. We will further code a C++ program to demonstrate the usage of the functions.

Binary search is one of the best searching algorithms used in programming. There are two more functions that use the same binary search approach and return the first and the last occurrences of an element in a vector or a data container. Today we will learn to implement these functions in C++.

Note: We can use the binary search and all its alternatives only over a monotonic search space. This means that the data must be sorted either in non-decreasing order or in non-increasing order.

In our examples, we will always consider non-decreasing data.

First Occurrence Function in C++

The first_occurrence() function returns the index where the target element appears for the first time. If the element is not present in the data structure, it simply returns the last index of the data structure.

This function is a modified form of the binary search algorithm. Whenever it discovers the target element, instead of simply returning the index of the element, it checks if the element is also present in the left portion of the data range.

Algorithm Code

For ease of understanding, we will return -1 instead of the last index to represent that the element is not present in the data.

int first_occurrence(vector <int> v, int start, int end, int target)
{
	// base case
	if(start > end)
		return -1;

	// otherwise we compare the mid element
	int mid = (start + end)/2;

	if(v[mid] == target)
	{
		// here's the change, instead of simply returning the
		// mid index, we check in the left part of the data
		// for remaining occurrences, by repeated binary searching
		if(first_occurrence(v, start, mid - 1, target) != -1)
			mid = first_occurrence(v, start, mid - 1, target);

		return mid;
	}
	else if(v[mid] < target)
	{
		// search in the right part
		return first_occurrence(v, mid + 1, end, target); 
	}
	else
	{
		// search in the left part
		return first_occurrence(v, start, mid - 1, target);
	}
}
First Occurrence Algorithm
First Occurrence Algorithm

Last Occurrence Function in C++

The last_occurrence() function returns the index where the target element appears for the lsat time. If the element is not present in the data structure, it simply returns -1.

This function is a modified form of the binary search algorithm. Whenever it discovers the target element, instead of simply returning the index of the element, it checks that if the element is also present in the left portion of the data range.

Algorithm Code

int last_occurrence(vector <int> v, int start, int end, int target)
{
	// base case
	if(start > end)
		return -1;

	// otherwise we compare the mid element
	int mid = (start + end)/2;

	if(v[mid] == target)
	{
		// here's the change, instead of simply returning the
		// mid index, we check in the right part of the data
		// for remaining occurrences, by repeated binary searching
		if(first_occurrence(v, start, mid - 1, target) != -1)
			mid = last_occurrence(v, mid + 1, end, target);

		return mid;
	}
	else if(v[mid] < target)
	{
		// search in the right part
		return last_occurrence(v, mid + 1, end, target); 
	}
	else
	{
		// search in the left part
		return last_occurrence(v, start, mid - 1, target);
	}
}
Last Occurrence Algorithm
Last Occurrence Algorithm

Program To Demonstrate The First And The Last Occurrence Functions in C++

Below is the code of the main function that demonstrates the first and last occurrence functions over a vector

// main function
int main()
{
	vector <int> v;
	cout << "Enter the elements, press -1 to stop !!!" << endl;

	while(true)
	{
		int ele;
		cin >> ele;

		if(ele == -1)
			break;

		v.push_back(ele);
	}

	print_vector(v);

	cout << "Now enter all the elements you want to find the first and the last occurrence of" << endl;

	vector <int> search_for;

	while(true)
	{
		int ele;
		cin >> ele;

		if(ele == -1)
			break;

		search_for.push_back(ele);
	}

	print_vector(search_for);

	cout << "The first and the last occurrences of the elements are:" << endl;

	for(int ele : search_for)
	{
		int first = first_occurrence(v, 0, v.size() - 1, ele);
		int last = last_occurrence(v, 0, v.size() - 1, ele);

		cout << "Element: " << ele << " First Occurrence: " << first << " Last Occurrence: " << last << endl;
	}

	return 0;
}
Main Function
Main Function

Output

First And Last Occurrence Program Output
First And Last Occurrence Program Output

Conclusion

In today’s article, we discussed two binary search derivates, the first occurrence, and the last occurrence algorithms. Later we coded first occurrence and last occurrence functions in C++. In the end, we wrote a C++ program to demonstrate the functionality of the first and the last occurrence functions.

The time complexity of the binary search is O(log2N), where N denotes the total number of elements in the data. Almost the same time complexity is observed for the first and the last occurrence algorithms since these are nothing just slight modifications to the binary search algorithm.

References

To read more about binary search, first occurrence, and last occurrence algorithms, you can refer to the following websites.

https://en.cppreference.com/w/cpp/algorithm/binary_search

https://en.cppreference.com/w/cpp/algorithm/find_first_of

https://en.cppreference.com/w/cpp/algorithm/find_end

close
Generic selectors
Exact matches only
Search in title
Search in content