Find the index of first occurrence of an element in a sorted array.

Question: Given a sorted array A of n elements, possibly with duplicates, find the index of the first occurrence of a number in O(log n) time.

Input: 4, 4, 8, 8, 8, 15, 16, 23, 23, 42. Find 8
Output: Index = 2 (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 first occurrence in the array, the number to the left of it must be smaller. We just add this condition to our loop.

if((mid == low && arr[mid] == data) || (arr[mid] == data && arr[mid-1] < data))

Here is the sample code for the same:-

#include<stdio.h>

int binarySearchFirstOccurrence(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 == low && arr[mid] == data) || (arr[mid] == data && arr[mid-1] < data))
			return mid;

		// We need to give preference to left part of the array
		// since we are concerned with the first occurrence
		else if(arr[mid] >= data)
			return binarySearchFirstOccurrence(arr, low, mid-1, data);
		else
			// We need to search in the right half
			return binarySearchFirstOccurrence(arr, mid+1, high, data);
	}
}

int getFirstOccurrence(int arr, int len, int data)
{
	int low = 0;
	int high = len - 1;

	int index = binarySearchFirstOccurrence(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 = getFirstOccurrence(arr, 11, 8);

	printf("The first occurrence is at = %d", result);

	return 0;
}

Time Complexity:- O(log n)
Space Complexity:- O(1)