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

Watch It Run

Try it yourself: Open TraceLit and step through every line.

---

Built with TraceLit — the visual algorithm tracer for LeetCode practice.

---

▲ 0 ▼ 0

Comments

Post Comment