Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding
Ninjas X Naukri.com

Last Updated: 27 Jun, 2016

Easy

```
You must write an algorithm whose time complexity is O(LogN)
```

```
The first line contains an Integer 'N', which denotes the size of the array/list.
The second line contains 'N' single space-separated integers representing the elements in the array/list.
The third line contains the value of 'target' to be searched for in the array/list.
```

```
Return the index at which 'target' is present for each test case, -1 otherwise.
```

```
1 <= N <= 10^5
1 <= A[i] <= 10^9
1 <= target <= 10^9
Time Limit: 1 sec
```

Since our array is sorted, we can apply binary search here. We will keep two variables, ‘s’ and ‘e’, initially assigned to ‘0’ and ‘length of the array’, respectively. At each iteration, we will first calculate the middle value of ‘s’ and ‘e’ and store it in a variable called ‘mid’. Then we will check the following conditions:

- nums[mid] == target:

We have found our answer in this case, so that we will return the index. - nums[mid] > target:

In this case, the current value is greater than the ‘target’, so we will go to the smaller values. - nums[mid] < target:

In this case, the current value is smaller than the ‘target’, so we will go to the larger values.

If we don’t find any index, we will return ‘-1’.

**// **Function to find the element ‘target’

**function **search**(int[] nums, int n, int target):**

**Int ‘n’ is the size of the array ‘nums’, and ‘target’ is the element we want to find.****Initialize two variables, ‘s’ and ‘e’, initially assigned to ‘0’ and ‘n - 1’, respectively.****while ‘s <= e’:**- Initialize a variable ‘mid’, and assign it to ‘(s + e) / 2’.
- If ‘nums[mid] == target’:
- Return ‘mid’.

- else if ‘nums[mid] > target’:
- Assign ‘e’ to ‘mid - 1’.

- else:
- Assign ‘s’ to ‘mid + 1’.

**Return -1.**

Similar problems

Ninja And The Strictly Increasing Array

Moderate

Posted: 27 Nov, 2022

Negative To The End

Easy

Posted: 16 Dec, 2022

Day 28 : Fake Coin Problem

Easy

Posted: 24 Dec, 2022

Day 28 : Fake Coin Problem

Easy

Posted: 24 Dec, 2022

Search In A Rotated Sorted Array II

Easy

Posted: 3 Feb, 2023

Find Duplicate in Array

Easy

Posted: 5 Jun, 2023