704. Binary Search

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

Table of Content

• Reference
• Problem Statement
• Approach
• Code
• Complexity

Reference: 704. Binary Search

Problem statement

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.

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.

Approach

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.

Code

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;
};

Complexity

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.