Find the first occurrence of an element in a sorted array

© Parineeth M R

Question 40. Find the first occurrence of a number in a sorted array


Consider the sorted array A = {10, 10, 20, 20, 30, 30, 30}. If we are asked to return the first occurrence of 30, then we return the index 4. If we are asked to return the first occurrence of a number not present in the array such as 15, then we return -1.

We can do this using modified binary search in O(logn). In normal binary search, we stop as soon as we find the element being searched. In the modified binary search, we continue the binary search if the found element is not the first occurrence of the element in the array. The code is given below

C/C++


/*
a: array being searched
n: number of elements in array
x: element being searched
Return value: first position of x in a, if x is absent -1 is returned
*/
int find_first(int a[], int n, int x)
{
	int start, end, mid;

	start = 0;
	end = n - 1;

	while (start <= end) {
		mid = (start + end) / 2;

		if (a[mid] == x) {
			if (mid == 0 || a[mid - 1] != x)
			     return mid;
			else
			     end = mid - 1;

		} else if (a[mid] > x) {
			end = mid - 1;
		} else {
			start = mid + 1;
		}
	}
	return -1;
}



Java


/*
a: array being searched
x: element being searched
Return value: first position of x in a, if x is absent -1 is returned
*/
public static int findFirst(int[] a, int x) {
	int n = a.length;
	int start = 0;
	int end = n - 1;

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

		if (a[mid] == x) {
			if (mid == 0 || a[mid - 1] != x)
			     return mid;
			else
			     end = mid - 1;

		} else if (a[mid] > x) {
			end = mid - 1;
		} else {
			start = mid + 1;
		}
	}
	return -1;
}



Python


#a: list being searched
#x: element being searched
#Return value: first position of x in a, if x is absent -1 is returned
def find_first(a, x) :
	n = len(a)
	start = 0
	end = n - 1

	while (start <= end) :
		mid = (start + end) // 2

		if (a[mid] == x) :
			if (mid == 0 or a[mid - 1] != x):
			     return mid
			else:
			     end = mid - 1

		elif (a[mid] > x) :
			end = mid - 1
		else :
			start = mid + 1
		
	return -1