Binary Search (Leetcode #704)

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.

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 <= 10<sup>4</sup>

• -10<sup>4</sup> < nums[i], target < 10<sup>4</sup>

• All the integers in nums are unique.

• nums is sorted in ascending order.

Answer

The main clue of this question is that we have to solve it in a time complexity of O(long). This means we have to solve it using binary search.

Binary Search

A binary search is an efficient algorithm used to find a target value within a sorted array by repeatedly dividing the search range in half. It compares the target value to the middle element of the array and adjusts the search range to either the left or right half based on this comparison. This process continues until the target is found or the search range is exhausted, resulting in a time complexity of O(log n).

Here's the code

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        l = 0
        r = len(nums) - 1
        while l <= r:
            mid = (l + r)//2
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                l = mid + 1
            else:
                r = mid - 1
        return -1

Most of the code is quite self-explanatory. However, there is one area I would like to focus on: the updates l = mid + 1 and r = mid - 1.

When I first solved this question, I wondered why we couldn't just use l = mid or r = mid since the potential time saved here is very small.

To answer this question, I would like to give an example:

Initial setup:

l = 0, r = 4 (indices of the array nums)

Array: [1, 2, 3, 4, 5]

Target: 6

First iteration:

Calculate mid: mid = (0 + 4) // 2 = 2

Check nums[mid]: nums[2] = 3

Since nums[2] < 6, update l to mid (incorrect update).

New boundaries:

l = 2

r = 4

Second iteration:

Calculate mid: mid = (2 + 4) // 2 = 3

Check nums[mid]: nums[3] = 4

Since nums[3] < 6, update l to mid (incorrect update).

New boundaries:

l = 3

r = 4

Third iteration:

Calculate mid: mid = (3 + 4) // 2 = 3

Check nums[mid]: nums[3] = 4

Since nums[3] < 6, update l to mid (incorrect update).

New boundaries:

l = 3

r = 4

Hence, we are now stuck in an infinite loop. So when you are doing a binary search, remember to add or subtract 1 when updating the left and right boundaries.

Time complexity:

Since this is a binary search question we know that the time complexity is O(long)

since we are cutting the input by half each time

Space complexity:

O(1) since we are only storing pointer and nothing else