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

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

0 comment

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)

0 comment

#### You may also like

This site uses Akismet to reduce spam. Learn how your comment data is processed.

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More