Binary Search LeetCode Problem 704 [Python Solution]

The easy, but always occurring Binary Search LeetCode problem presents the challenge of creating an algorithm with a runtime complexity of O(log n), by the way, that’s the default binary search algorithm runtime.

Problem Overview

Question

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 returns its index. Otherwise, return -1. You must write an algorithm with O(log n) runtime complexity.

…

In the problem of binary search, we’re given an array of integers nums, which is sorted in ascending order.

We’re also given an integer target that we need to find within the array.

If the target exists in nums, we should return its index; otherwise, we return -1.

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 we return -1.

Understanding Binary Search Constraints

Before we dive into the solution, let’s understand the constraints of this problem:

Array Length: The length of the nums array can vary, ranging from as short as 1 element to as long as 10,000 elements.
Value Range: Both the elements within the nums array and the target value can be any integer within the range of -10,000 to 10,000. This means the numbers you’re working with will fall within this specific numerical range.
Unique Numbers: Each integer within the nums array is unique, meaning there are no duplicate values. You won’t encounter the same number repeated within the array.
Sorted Order: The nums array is sorted in ascending order. This arrangement ensures that the integers within the array are organized from smallest to largest, making it suitable for applying the binary search algorithm efficiently.

Efficient Solution: Binary Search

Binary search is the key to solving this problem efficiently. The basic idea of binary search is to repeatedly divide the search interval in half.

We start with the entire array, and in each iteration, we check the middle element of the current interval and compare it with the target value.

Based on this comparison, we can eliminate half of the remaining possibilities and continue the search in the remaining half.

Here’s the Python code for the efficient binary search approach:

View on GitHub ➹

def search(self, nums: List[int], target: int) -> int:
    left, right = 0, len(nums) - 1

    while left <= right:
        middle = left + ((right - left) // 2)  # Prevent overflow
        if nums[middle] > target:
            right = middle - 1
        elif nums[middle] &lt; target:
            left = middle + 1
        else:
            return middle
    
    return -1

In this code, we initialize two pointers, left and right, to define the search interval.

We then enter a loop that continues as long as left is less than or equal to right.

Within the loop, we calculate the middle index to check the element at that position.

If nums[middle] is greater than target, we update the right pointer to middle - 1, effectively eliminating the right half of the interval.
If nums[middle] is less than target, we update the left pointer to middle + 1, eliminating the left half.
If nums[middle] is equal to target, we have found the target, and we return the index (middle).

If we exit the loop without finding the target, we return -1 to indicate that the target does not exist in the array.

Time and Space Complexity

The time complexity of this binary search algorithm is O(log n) because, in each iteration, we divide the search interval in half.

This is a highly efficient algorithm for finding an element in a sorted array.

The space complexity is O(1) because we only use a constant amount of extra space for the pointers and variables.

Reasoning Behind Our Approach

The reasoning behind the binary search approach lies in its ability to quickly eliminate half of the possibilities in each step.

By comparing the middle element to the target value, we determine whether the target is likely to be in the left or right half of the interval.

This efficient divide-and-conquer strategy reduces the search space exponentially, resulting in a logarithmic runtime complexity.

In summary, binary search is a powerful technique for efficiently finding elements in sorted arrays and understanding its principles is essential for tackling various algorithmic challenges.

Conclusion

In this article, we explored the binary search algorithm and its application to the LeetCode problem 704.

We learned how to efficiently find a target element in a sorted array, even when dealing with large datasets.

Binary search is a fundamental algorithm to have in your problem-solving toolkit, and mastering it will help you tackle a wide range of coding challenges.

Feel free to comment with any questions, suggestions, or additional topics you’d like to learn about. Happy coding!