Binary Search (#704)

Problem Statement

Link: LeetCode

Complexity: 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.

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


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

Solution Explanation:

To achieve a time complexity of O(log n), we can use binary search algorithm.

The idea of binary search is to divide the search space in half at each step. We start by setting two pointers, ‘left‘ and 'right‘, to the beginning and end of the array, respectively. We then calculate the midpoint of the search space as mid = '(left + right) // 2.

We compare the value at the midpoint nums'[mid]' with the target value. If they are equal, we have found the target and return its index mid. If ‘nums[mid] < target‘, we know that the target must be in the right half of the search space, so we move the left pointer to ‘mid + 1‘. Otherwise, we move the right pointer to mid - 1‘.

We repeat this process until we find the target or the search space is empty, which is when ‘left > right‘. If we don’t find the target by then, we return -1.

The time complexity of this algorithm is O(log n) because we divide the search space in half at each step, which reduces the search space exponentially.

Let’s understand it with an example:

We have a sorted array: [1, 3, 4, 6, 8, 9, 11], and we need to find 4 in it.

We’d initialise the pointers to extreme ends of array, i.e., left pointer to 0 and right pointer to 1.

Then, we’ll find the middle element, the middle element is 6.

mid = (left + right) // 2 = (0 + 6) // 2 = 3

Since the middle element is greater than the target, the target must be in the left half of the search range.

Leet Code Binary Search Solution
We’ll repeat the process until we find the solution or dataset is empty.

Solution Code:
Solution 1

By using ‘enumerate‘. It is a built-in Python function that returns an iterator of tuples containing indices and values from an iterable.

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        for indx, num in enumerate(nums):
            if num == target:
                return indx
        return -1
Solution 2

Using binary search, where we divide the sorted array in half repeatedly until the target element is found, or the search space is empty

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = (right + left) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                left = mid + 1
                right = mid - 1
        return -1

Leave a Comment

Your email address will not be published. Required fields are marked *

Scroll to Top