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: 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 exists in the array.

Try it yourself

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 the Boundary module.

Time Complexity: O(log(n))

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)
22
1import 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}
38
1using 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}
45
1function 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}
47
1#include <algorithm> // copy
2#include <iostream> // 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    std::vector<T> v;
31    std::copy(std::istream_iterator<T>{ss}, std::istream_iterator<T>{}, std::back_inserter(v));
32    return v;
33}
34
35void ignore_line() {
36    std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
37}
38
39int main() {
40    std::vector<int> arr = get_words<int>();
41    int target;
42    std::cin >> target;
43    ignore_line();
44    int res = find_first_occurrence(arr, target);
45    std::cout << res << '\n';
46}
47
1import 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
22