Day 8 - Binary Search

🧩 Problem:

Given a sorted array of integers nums and an integer target, return the index of target if it exists in the array. Otherwise, return -1.

You must solve it with O(log n) time complexity.

🧪 Examples:

Example 1
Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4

Example 2
Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1

📏 Constraints:

• 1 <= nums.length <= 10^4

• -10^4 < nums[i], target < 10^4

• All elements in nums are unique and sorted in ascending order

🧠 How to Approach It

This is the classic binary search pattern:

• Keep a left and right pointer

• Check the mid index

• If nums[mid] == target, return mid

• If nums[mid] < target, discard the left half

• If nums[mid] > target, discard the right half

Repeat until you find the target or the range is invalid.

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

✅ Python Solution:

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

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

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

        return -1

💬 TL;DR:

Binary Search is one of the most efficient ways to work with sorted arrays.

• Always check if sorting allows you to cut the search space in half.

• You’ll use this pattern a lot in interviews.