Question

LeetCode Link | 704. Binary Search | Easy

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

You must write an algorithm with O(log n) runtime complexity.

Constrains

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

Examples

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

Solution Approach

Constrains

  • Sorted list
  • Unique values

The premise of this problem is that the array is sorted, and the problem also emphasizes that there are no duplicate elements in the array, because if there are duplicate elements, the index of the element returned by the binary search may not be unique. These are the prerequisites for using binary search. When you see that the problem description meets the above conditions, you might want to consider whether binary search can be used.

Concept Explanation

We define the target to be within a closed interval, specifically [left, right]. The definition of the interval determines how the binary search code should be written. Because the target is defined to be within the [left, right] interval, there are the following two points:

  • Use while (left <= right) with <=, because left == right is meaningful, so we use <=.
  • If nums[middle] > target, assign right = middle - 1, because the current nums[middle] is definitely not the target. Therefore, the next search should end at middle - 1 for the left interval.

Binary Search

Code

  • Time complexity: O(log n)
  • Space complexity: O(1)

TypeScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function search(nums: number[], target: number): number {
    let mid: number, left: number = 0, right: number = nums.length - 1;
    while (left <= right) {
        // bitwise operations, preventing overflow of large numbers.
        mid = left + ((right - left) >> 1);
        if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            return mid;
        }
    }
    return -1;
};

Conclusion

Binary search is a very important fundamental algorithm. Just remember that it requires a ordered/sorted array and all values must be unique in array. Have a clear understanding of the intervals in array should be good enough to write binary search.