New update is available. Click here to update.

Last Updated: 30 Oct, 2020

Difficulty: Easy

```
If the given array 'A' is: [1, 2, 4, 7] and M = 6. We insert M = 6 in the array and get 'A' as: [1, 2, 4, 6, 7]. The position of 6 is 3 (according to 0-based indexing)
```

```
1) The given array has distinct integers.
2) The given array may be empty.
```

```
The first line contains two space-separated integers 'N' and 'M', representing the length of the array and the target integer.
The second line contains 'N' space-separated integers, Ai representing the given array.
```

```
Print a single line containing a single integer denoting the position of 'M' in the final array, on a new line.
```

```
You do not need to print anything, it has already been taken care of. Just implement the given function.
```

```
0 ≤ N ≤ 10 ^ 5
1 ≤ M ≤ 10 ^ 9
1 ≤ Ai ≤ 10 ^ 9
Where 'Ai' is the array element at index 'i'.
Time Limit: 1 sec.
```

```
Try to solve the problem in O(log N).
```

- Take two pointers L = 0 and R = N - 1 and mid = L + (R - L) / 2, pos = 0.
- Using binary search, there can be three conditions:
- A[mid] == M, return mid.
- A[mid] > M, set R = mid - 1. Along with this, set pos = i (since this can be a possible answer)
- A[mid] < M, set L = mid + 1.

- Return the answer which would be pos.

SIMILAR PROBLEMS

Merge Two Sorted Arrays Without Extra Space

Posted: 19 Nov, 2022

Difficulty: Moderate

Search In A Sorted 2D Matrix

Posted: 23 Nov, 2022

Difficulty: Moderate

Ninja And The Strictly Increasing Array

Posted: 27 Nov, 2022

Difficulty: Moderate

Negative To The End

Posted: 16 Dec, 2022

Difficulty: Easy

Fake Coin Problem

Posted: 24 Dec, 2022

Difficulty: Easy

Popular Interview Problems: