Binary Search - Classic Problems | Repovive

CLS26. Binary Search

1s256 MB

Given a sorted array of $n$ integers in non-decreasing order and a target value $x$ , find the index of the first occurrence of $x$ in the array.

Output the 1-indexed position, or $-1$ if $x$ is not found.

\begin{array}{l} n \quad x \\ a_1 \quad a_2 \quad \cdots \quad a_n \end{array}

\begin{cases} \text{index (1-indexed)} & \text{if found} \\ -1 & \text{otherwise} \end{cases}

Input

5 3
1 2 3 4 5

Explanation

For this input, the required output is 3.

Output

Input

5 6
1 2 3 4 5

Explanation

For this input, the required output is -1.

Output

-1

Input

7 2
1 2 2 2 3 4 5

Explanation

For this input, the required output is 2.

Output

1s256 MB

Given a sorted array of $n$ integers in non-decreasing order and a target value $x$ , find the index of the first occurrence of $x$ in the array.

Output the 1-indexed position, or $-1$ if $x$ is not found.

\begin{array}{l} n \quad x \\ a_1 \quad a_2 \quad \cdots \quad a_n \end{array}

\begin{cases} \text{index (1-indexed)} & \text{if found} \\ -1 & \text{otherwise} \end{cases}

Input

5 3
1 2 3 4 5

Explanation

For this input, the required output is 3.

Output

Input

5 6
1 2 3 4 5

Explanation

For this input, the required output is -1.

Output

-1

Input

7 2
1 2 2 2 3 4 5

Explanation

For this input, the required output is 2.

Output