LeetCode Problems

In this tutorial we will solve 704. Binary Search from leetcode.

Reference: 704. Binary Search

In this problem statement we are given an array of integer values `nums`

which is already sorted in ascending order. We are also given an integer value `target`

. We are asked to find `target`

in the input array `nums`

and return the index. If `target`

is not present in the input array then we are asked to return `-1`

.

Watch this video for Binary Search.

Example from leetcode.

```
Example 1:
Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4
Example 2:
Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1
```

```
Constraints:
1 <= nums.length <= 104
-10^4 < nums[i], target < 10^4
All the integers in nums are unique.
nums is sorted in ascending order.
```

We use binary search to search an item in a given array which is already in ascending/descending order. We begin by first taking the middle element of the array. This middle element divides the array into two parts, the left part and the right part. Then we compare the target element with the middle element. If the target element is equal to the middle element then we return the index of the middle element. If the target element is smaller than the middle element then we continue our search in the left part. Otherwise, we will continue our search in the right part. This way, we will be search only half of the array each time.

Consider the following input nums [-1,0,3,5,9,12] and target 9.

```
target = 9
index = 0 1 2 3 4 5
nums = [-1, 0, 3, 5, 9, 12]
let us start by taking the start and end index of the array.
start = 0
end = 5
while start <= end ? YES
mid = floor((start + end) / 2)
= floor((0+5)/2)
= floor(2.5)
= 2
is midValue == target ?
i.e., nums[2] == 9 ?
i.e., 3 == 9 ? NO
3 is less than 9, therefore we will search the right part
start = mid + 1
= 2 + 1
= 3
end = 5
while start <= end ? YES
mid = floor((start + end) / 2)
= floor((3+5)/2)
= floor(4)
= 4
is midValue == target ?
i.e., nums[4] == 9 ?
i.e., 9 == 9 ? YES
we found the target!
it is at index 4.
```

JavaScript

```
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var search = function(nums, target) {
let start = 0;
let end = nums.length - 1;
while(start <= end) {
const mid = Math.floor((start+end)/2);
if (nums[mid] === target) return mid;
if (nums[mid] < target) start = mid + 1;
else end = mid - 1;
}
return -1;
};
```

**Time complexity: O(log n)**

The time complexity of Binary search is O(log n) where n is the number of elements in the input array.

**Space complexity: O(1)**

The space complexity is constant for Binary Search.

ADVERTISEMENT