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)
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> // 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}
48
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

Still not clear? Submit the part you don't understand to our editors.