© 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