Binary Search in Python Explained | LeetCode 704 Solution with Time & Space Complexity

Binary Search in Python – Simple and Efficient Approach (LeetCode 704)

Today I solved LeetCode 704: Binary Search, and the problem felt quite straightforward since I was already familiar with the binary search concept. This problem is a classic example of how knowing the fundamentals can make problem-solving much easier.

The task is simple: given a sorted array of integers and a target value, return the index of the target if it exists. Otherwise, return -1. Since the array is already sorted, binary search is the most optimal approach.

Why Binary Search?

Binary search works by repeatedly dividing the search space in half. Instead of checking every element one by one, we compare the middle element with the target and eliminate half of the array in each step. This drastically improves performance compared to a linear search.

Approach Explained

• Initialize two pointers: start at the beginning and end at the end of the array.
• Calculate the middle index using (start + end) // 2.
• If the middle element equals the target, return its index.
• If the middle element is greater than the target, search the left half.
• If the middle element is smaller than the target, search the right half.
• Repeat until the search space is exhausted.

Python Implementation

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        s = 0
        e = len(nums) - 1

        while s <= e:
            mid = (s + e) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] > target:
                e = mid - 1
            else:
                s = mid + 1
        
        return -1

    

Time and Space Complexity

Metric	Complexity
Time Complexity	O(log n)
Space Complexity	O(1)

The time complexity is O(log n) because the search space is halved in every iteration. The space complexity remains O(1) since no extra data structures are used.

Source Code

You can find the complete solution on GitHub here: Binary Search – LeetCode 704 (Python)

Problems like this reinforce the importance of mastering core algorithms. Once the fundamentals are clear, solutions often feel simple and intuitive.