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 = 0
5 r = len(arr) - 1
6 ans = -1
7 while l <= r:
8 mid = (l + r) // 2
9 if arr[mid] == target:
10 ans = mid
11 r = mid - 1
12 elif arr[mid] < target:
13 l = mid + 1
14 else:
15 r = mid - 1
16 return ans
17
18if __name__ == "__main__":
19 arr = [int(x) for x in input().split()]
20 target = int(input())
21 res = find_first_occurrence(arr, target)
22 print(res)
231import 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}
451"use strict";
2
3function findFirstOccurrence(arr, target) {
4 let left = 0;
5 let right = arr.length - 1;
6 let targetIndex = -1;
7 while (left <= right) {
8 const mid = Math.floor((left + right) / 2);
9 if (arr[mid] === target) {
10 targetIndex = mid;
11 right = mid - 1;
12 } else if (arr[mid] < target) {
13 left = mid + 1;
14 } else {
15 right = mid - 1;
16 }
17 }
18 return targetIndex;
19}
20
21function splitWords(s) {
22 return s === "" ? [] : s.split(" ");
23}
24
25function* main() {
26 const arr = splitWords(yield).map((v) => parseInt(v));
27 const target = parseInt(yield);
28 const res = findFirstOccurrence(arr, target);
29 console.log(res);
30}
31
32class EOFError extends Error {}
33{
34 const gen = main();
35 const next = (line) => gen.next(line).done && process.exit();
36 let buf = "";
37 next();
38 process.stdin.setEncoding("utf8");
39 process.stdin.on("data", (data) => {
40 const lines = (buf + data).split("\n");
41 buf = lines.pop();
42 lines.forEach(next);
43 });
44 process.stdin.on("end", () => {
45 buf && next(buf);
46 gen.throw(new EOFError());
47 });
48}
491#include <algorithm>
2#include <iostream>
3#include <iterator>
4#include <limits>
5#include <sstream>
6#include <string>
7#include <vector>
8
9int find_first_occurrence(std::vector<int> arr, int target) {
10 int left = 0;
11 int right = arr.size() - 1;
12 int target_index = -1;
13 while (left <= right) {
14 int mid = left + (right - left) / 2;
15 if (arr[mid] == target) {
16 target_index = mid;
17 right = mid - 1;
18 } else if (arr[mid] < target) {
19 left = mid + 1;
20 } else {
21 right = mid - 1;
22 }
23 }
24 return target_index;
25}
26
27template<typename T>
28std::vector<T> get_words() {
29 std::string line;
30 std::getline(std::cin, line);
31 std::istringstream ss{line};
32 ss >> std::boolalpha;
33 std::vector<T> v;
34 std::copy(std::istream_iterator<T>{ss}, std::istream_iterator<T>{}, std::back_inserter(v));
35 return v;
36}
37
38void ignore_line() {
39 std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
40}
41
42int main() {
43 std::vector<int> arr = get_words<int>();
44 int target;
45 std::cin >> target;
46 ignore_line();
47 int res = find_first_occurrence(arr, target);
48 std::cout << res << '\n';
49}
501package main
2
3import (
4 "bufio"
5 "fmt"
6 "os"
7 "strconv"
8 "strings"
9)
10
11func findFirstOccurrence(arr []int, target int) int {
12 l := 0
13 r := len(arr) - 1
14 ans := -1
15 for l <= r {
16 mid := (l + r) / 2
17 if arr[mid] == target {
18 ans = mid
19 r = mid - 1
20 } else if arr[mid] < target {
21 l = mid + 1
22 } else {
23 r = mid - 1
24 }
25 }
26 return ans
27}
28
29func arrayAtoi(arr []string) []int {
30 res := []int{}
31 for _, x := range arr {
32 v, _ := strconv.Atoi(x)
33 res = append(res, v)
34 }
35 return res
36}
37
38func splitWords(s string) []string {
39 if s == "" {
40 return []string{}
41 }
42 return strings.Split(s, " ")
43}
44
45func main() {
46 scanner := bufio.NewScanner(os.Stdin)
47 scanner.Scan()
48 arr := arrayAtoi(splitWords(scanner.Text()))
49 scanner.Scan()
50 target, _ := strconv.Atoi(scanner.Text())
51 res := findFirstOccurrence(arr, target)
52 fmt.Println(res)
53}
541import Data.Array (Array)
2import Data.Array.IArray (bounds, listArray)
3import qualified Data.Array.IArray as A
4
5findFirstOccurrence :: Array Int Int -> Int -> Int
6findFirstOccurrence arr target = uncurry (search (-1)) $ bounds arr
7 where
8 search t l r
9 | l <= r = case compare (arr A.! m) target of
10 EQ -> search m l (pred m)
11 LT -> search t (succ m) r
12 GT -> search t l (pred m)
13 | otherwise = t
14 where
15 m = l + (r - l) `div` 2
16
17main :: IO ()
18main = do
19 arr' <- map read . words <$> getLine
20 let arr = listArray (0, length arr' - 1) arr'
21 target <- readLn
22 let res = findFirstOccurrence arr target
23 print res
24