LeetCode 704: Binary Search — Step-by-Step Visual Trace

#leetcode #python #algorithms

Easy — Binary Search | Array | Divide and Conquer

The Problem

Given a sorted array of integers and a target value, return the index of the target if it exists in the array, otherwise return -1. The algorithm must run in O(log n) time complexity.

Approach

Use binary search to efficiently find the target by repeatedly dividing the search space in half. Compare the middle element with the target and adjust the search boundaries accordingly until the target is found or the search space is exhausted.

Time: O(log n) · Space: O(1)

Code

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

        while left <= right:
            mid = left + (right - left) // 2

            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1

        return -1