# Find Element in Sorted Array with Duplicates

Given a sorted array of integers and a target integer, find the first occurrence of the target and return its index. Return -1 if the target is not in the array.

Input:

``````arr = [1, 3, 3, 3, 3, 6, 10, 10, 10, 100]
target = 3``````

Output:

``1``

Explanation: First occurrence of 3 is at index 1.

## Explanation

The problem is equivalent to finding the boundary of elements < 3 and elements >= 3. Imagine we apply a filter of `arr[i] >= 3`, we would get: Now the problem is reduced to finding the first `true` element in a boolean array. And we already know how to do this from Find Boundary module.

Time Complexity: `O(log(n))`

## Implementation

 `1` `1` ``from typing import List`` `2` `2` `3` `3` ``def find_first_occurrence(arr: List[int], target: int) -> int:`` `4` `-` `` # WRITE YOUR BRILLIANT CODE HERE`` `4` `+` `` l, r = 0, len(arr) - 1`` `5` `-` `` return 0`` `5` `+` `` ans = -1`` `6` `+` `` while l <= r:`` `7` `+` `` mid = (l + r) // 2`` `8` `+` `` if arr[mid] == target:`` `9` `+` `` ans = mid`` `10` `+` `` r = mid - 1`` `11` `+` `` elif arr[mid] < target:`` `12` `+` `` l = mid + 1`` `13` `+` `` else:`` `14` `+` `` r = mid - 1`` `15` `+` `` return ans`` `16` `+` `6` `17` ``if __name__ == '__main__':`` `7` `18` `` arr = [int(x) for x in input().split()]`` `8` `19` `` target = int(input())`` `9` `20` `` res = find_first_occurrence(arr, target)`` `10` `21` `` print(res)``