Binary Search

Problem Summary

(Write in your own words, not copied from LeetCode. This forces comprehension.)

• Given a sorted array, find the target element in $O(logn)$

Key Observations

(Patterns, constraints, or hints in the problem statement.)

• Input array is sorted

Main Concepts Used

(Mark the CS concepts or algorithms used.)

• Array
• Binary Search

Time & Space Complexity

• Time: $O(logn)$ → Reason: Cutting down the search space by half on each iteration
• Space: $O(1)$ → Reason: No extra memory used

Code

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

        while l <= r:
            m = (l + r) // 2
            cur = nums[m]
            if cur == target:
                return m
            elif cur > target:
                r = m - 1
            else:
                l = m + 1
        return -1

Common Mistakes / Things I Got Stuck On

• Use l <= r instead of l < r, think of 1 element array