Find Element in Sorted Array with Duplicates
Prereq: Vanilla Binary Search and Finding the Boundary with Binary Search
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: The first occurrence of 3 is at index 1.
Input:
arr = [2, 3, 5, 7, 11, 13, 17, 19]target = 6
Output: -1
Explanation:
6 does not exist in the array.
Try it yourself
Explanation
The problem is equivalent to finding the boundary of elements < 3 and elements >= 3.
As we go from the left to the right of the sorted array, once we see an element equal to 3, the rest of the array should also be greater than or equal to 3.
The feasible function is arr[i] >= 3.
Now the problem is reduced to finding the first true element in a boolean array. And we already know how to do this from the Find the First True in a Sorted Boolean Array module.
Time Complexity: O(log(n))
Space Complexity: O(1)
Caveat: note that the feasible function checks whether the element is greater than or equal to the target.
But the question asks for the index of the first element exactly equal to the target.
Our template updates ans = mid whenever arr[mid] >= target.
Therefore we have to make a small modification to the template and move ans = mid to only when arr[mid] == target and not arr[mid] >= target.
Implementation
1from typing import List
2
3def find_first_occurrence(arr: List[int], target: int) -> int:
4 l, r = 0, len(arr) - 1
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
17if __name__ == '__main__':
18 arr = [int(x) for x in input().split()]
19 target = int(input())
20 res = find_first_occurrence(arr, target)
21 print(res)
221import java.util.Arrays;
2import java.util.List;
3import java.util.Scanner;
4import java.util.stream.Collectors;
5
6class Solution {
7 public static int findFirstOccurrence(List<Integer> arr, int target) {
8 int targetIndex = -1;
9 int left = 0;
10 int right = arr.size() - 1;
11 while (left <= right) {
12 int mid = left + (right - left) / 2;
13 if (arr.get(mid) == target) {
14 targetIndex = mid;
15 right = mid - 1;
16 } else if (arr.get(mid) < target) {
17 left = mid + 1;
18 } else {
19 right = mid - 1;
20 }
21 }
22 return targetIndex;
23 }
24
25 public static List<String> splitWords(String s) {
26 return s.isEmpty() ? List.of() : Arrays.asList(s.split(" "));
27 }
28
29 public static void main(String[] args) {
30 Scanner scanner = new Scanner(System.in);
31 List<Integer> arr = splitWords(scanner.nextLine()).stream().map(Integer::parseInt).collect(Collectors.toList());
32 int target = Integer.parseInt(scanner.nextLine());
33 scanner.close();
34 int res = findFirstOccurrence(arr, target);
35 System.out.println(res);
36 }
37}
381using System;
2using System.Collections.Generic;
3using System.Linq;
4
5class Solution
6{
7 public static int FindFirstOccurrence(List<int> arr, int target)
8 {
9 int targetIndex = -1;
10 int left = 0;
11 int right = arr.Count - 1;
12 while (left <= right)
13 {
14 int mid = left + (right - left) / 2;
15 if (arr[mid] == target)
16 {
17 targetIndex = mid;
18 right = mid - 1;
19 }
20 else if (arr[mid] < target)
21 {
22 left = mid + 1;
23 }
24 else
25 {
26 right = mid - 1;
27 }
28 }
29 return targetIndex;
30 }
31
32 public static List<string> SplitWords(string s)
33 {
34 return string.IsNullOrEmpty(s) ? new List<string>() : s.Trim().Split(' ').ToList();
35 }
36
37 public static void Main()
38 {
39 List<int> arr = SplitWords(Console.ReadLine()).Select(int.Parse).ToList();
40 int target = int.Parse(Console.ReadLine());
41 int res = FindFirstOccurrence(arr, target);
42 Console.WriteLine(res);
43 }
44}
451function findFirstOccurrence(arr, target) {
2 let left = 0;
3 let right = arr.length - 1;
4 let targetIndex = -1;
5 while (left <= right) {
6 let mid = Math.floor((left + right) / 2);
7 if (arr[mid] == target) {
8 targetIndex = mid;
9 right = mid - 1;
10 } else if (arr[mid] < target) {
11 left = mid + 1;
12 } else {
13 right = mid - 1;
14 }
15 }
16 return targetIndex;
17}
18
19function splitWords(s) {
20 return s == "" ? [] : s.split(' ');
21}
22
23function* main() {
24 const arr = splitWords(yield).map((v) => parseInt(v));
25 const target = parseInt(yield);
26 const res = findFirstOccurrence(arr, target);
27 console.log(res);
28}
29
30class EOFError extends Error {}
31{
32 const gen = main();
33 const next = (line) => gen.next(line).done && process.exit();
34 let buf = '';
35 next();
36 process.stdin.setEncoding('utf8');
37 process.stdin.on('data', (data) => {
38 const lines = (buf + data).split('\n');
39 buf = lines.pop();
40 lines.forEach(next);
41 });
42 process.stdin.on('end', () => {
43 buf && next(buf);
44 gen.throw(new EOFError());
45 });
46}
471#include <algorithm> // copy
2#include <iostream> // boolalpha, cin, cout, streamsize
3#include <iterator> // back_inserter, istream_iterator
4#include <limits> // numeric_limits
5#include <sstream> // istringstream
6#include <string> // getline, string
7#include <vector> // vector
8
9int find_first_occurrence(std::vector<int> arr, int target) {
10 int left = 0, right = arr.size() - 1, target_index = -1;
11 while (left <= right) {
12 int mid = left + (right - left) / 2;
13 if (arr[mid] == target) {
14 target_index = mid;
15 right = mid - 1;
16 } else if (arr[mid] < target) {
17 left = mid + 1;
18 } else {
19 right = mid - 1;
20 }
21 }
22 return target_index;
23}
24
25template<typename T>
26std::vector<T> get_words() {
27 std::string line;
28 std::getline(std::cin, line);
29 std::istringstream ss{line};
30 ss >> std::boolalpha;
31 std::vector<T> v;
32 std::copy(std::istream_iterator<T>{ss}, std::istream_iterator<T>{}, std::back_inserter(v));
33 return v;
34}
35
36void ignore_line() {
37 std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
38}
39
40int main() {
41 std::vector<int> arr = get_words<int>();
42 int target;
43 std::cin >> target;
44 ignore_line();
45 int res = find_first_occurrence(arr, target);
46 std::cout << res << '\n';
47}
481import Data.Array (Array)
2import qualified Data.Array.IArray as A
3import Data.Array.IArray (bounds, listArray)
4
5findFirstOccurrence :: Array Int Int -> Int -> Int
6findFirstOccurrence arr target = uncurry (search (-1)) $ bounds arr where
7 search t l r
8 | l <= r = case compare (arr A.! m) target of
9 EQ -> search m l (pred m)
10 LT -> search t (succ m) r
11 GT -> search t l (pred m)
12 | otherwise = t
13 where m = l + (r - l) `div` 2
14
15main :: IO ()
16main = do
17 arr' <- map read . words <$> getLine
18 let arr = listArray (0, length arr' - 1) arr'
19 target <- readLn
20 let res = findFirstOccurrence arr target
21 print res
22Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.