Find Element in Sorted Array with Duplicates

Prereq: Finding 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:

Explanation: First occurrence of 3 is at index 1.

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

Implementation

def find_first_occurrence(arr, target):
    # WRITE YOUR BRILLIANT CODE HERE
    l, r = 0, len(arr) - 1
    ans = -1
    while l <= r:
        mid = (l + r) // 2
        if arr[mid] == target:
            ans = mid
            r = mid - 1
        elif arr[mid] < target:
            l = mid + 1
        else:
            r = mid - 1
    return ans

if __name__ == '__main__':
    arr = [int(x) for x in input().split()]
    target = int(input())
    print(find_first_occurrence(arr, target))

Expand 4 lines ...
class Solution {

    public static int findFirstOccurrence(int[] arr, int target) {
        // WRITE YOUR BRILLIANT CODE HERE
        int targetIndex = -1;
        int left = 0;
        int right = arr.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (arr[mid] == target) {
                targetIndex = mid;
                right = mid - 1;
            } else if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return targetIndex;
    }

    public static void main(String[] args) throws IOException {
        Scanner scanner = new Scanner(System.in);
Expand 6 lines ...

const readline = require('readline');

function find_first_occurrence(arr, target) {
    // WRITE YOUR BRILLIANT CODE HERE
    let left = 0;
    let right = arr.length - 1;
    let target_index = -1;
    while (left <= right) {
        let mid = left + Math.trunc((right - left) / 2);
        if (arr[mid] == target) {
            target_index = mid;
            right = mid - 1;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return target_index;
}

const rl = readline.createInterface(process.stdin);
const inputs = [];
Expand 7 lines ...

import           Data.Array (Array, listArray)
import           Data.Array (Array, bounds, listArray, (!))

findFirstOccurrence :: Array Int Int -> Int -> Int
findFirstOccurrence arr target = -- WRITE YOUR BRILLIANT CODE HERE
findFirstOccurrence arr target = uncurry (search (-1)) $ bounds arr where
  search t l r
    | l <= r = case compare (arr ! m) target of
        EQ -> search m l (pred m)
        LT -> search t (succ m) r
        GT -> search t l (pred m)
    | otherwise = t
    where m = l + (r - l) `div` 2

main :: IO ()
main = do
  arr' <- map read . words <$> getLine
  target <- read <$> getLine
  let arr = listArray (0, length arr' - 1) arr'
Expand 2 lines ...

Loading full content...

Join our community on Discord

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

			Expand 4 lines ...
5	5		`class Solution {`
6	6
7	7		`public static int findFirstOccurrence(int[] arr, int target) {`
8		-	`// WRITE YOUR BRILLIANT CODE HERE`
	8	+	`int targetIndex = -1;`
	9	+	`int left = 0;`
	10	+	`int right = arr.length - 1;`
	11	+	`while (left <= right) {`
	12	+	`int mid = (left + right) / 2;`
	13	+	`if (arr[mid] == target) {`
	14	+	`targetIndex = 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 targetIndex;`
9	23		`}`
10	24
11	25		`public static void main(String[] args) throws IOException {`
12	26		`Scanner scanner = new Scanner(System.in);`
			Expand 6 lines ...

1	1		`const readline = require('readline');`
2	2
3	3		`function find_first_occurrence(arr, target) {`
4		-	`// WRITE YOUR BRILLIANT CODE HERE`
	4	+	`let left = 0;`
	5	+	`let right = arr.length - 1;`
	6	+	`let target_index = -1;`
	7	+	`while (left <= right) {`
	8	+	`let mid = left + Math.trunc((right - left) / 2);`
	9	+	`if (arr[mid] == target) {`
	10	+	`target_index = 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 target_index;`
5	19		`}`
6	20
7	21		`const rl = readline.createInterface(process.stdin);`
8	22		`const inputs = [];`
			Expand 7 lines ...

1		-	`import Data.Array (Array, listArray)`
	1	+	`import Data.Array (Array, bounds, listArray, (!))`
2	2
3	3		`findFirstOccurrence :: Array Int Int -> Int -> Int`
4		-	`findFirstOccurrence arr target = -- WRITE YOUR BRILLIANT CODE HERE`
	4	+	`findFirstOccurrence arr target = uncurry (search (-1)) $ bounds arr where`
	5	+	`search t l r`
	6	+	`\| l <= r = case compare (arr ! m) target of`
	7	+	`EQ -> search m l (pred m)`
	8	+	`LT -> search t (succ m) r`
	9	+	`GT -> search t l (pred m)`
	10	+	`\| otherwise = t`
	11	+	where m = l + (r - l) `div` 2
	12	+
5	13		`main :: IO ()`
6	14		`main = do`
7	15		`arr' <- map read . words <$> getLine`
8	16		`target <- read <$> getLine`
9	17		`let arr = listArray (0, length arr' - 1) arr'`
			Expand 2 lines ...

Progress

Getting Started

Overview

Basic Data Structures

Binary Search

Overview

Sorted Array

Implicitly Sorted Array

Depth First Search/ Backtracking

Introduction

DFS on Tree

Combinatorial Search

Memoization

Breadth First Search

Introduction

BFS on Tree

Graph

Introduction

BFS

Matrix as Graph

Directed Graph

Two Pointers

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Priority Queue / Heap

Introduction

Top K

Advanced

Divide and Conquer

Introduction

Generalized

Binary Search

Dynamic Programming

Introduction

Sequence

Grid

Dynamic number of subproblems

Partition

Two Sequences

Game Theory

Other

Monotonic Stack

Data Structure Design

Company Specific

Amazon OA

Find Element in Sorted Array with Duplicates

Try it yourself

Explanation

Implementation