Binary Search

Difficulty: Easy | Acceptance: 60.80% | Paid: No Topics: Array, Binary Search

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. otherwise, return -1.

You must write an algorithm with O(log n) runtime complexity.

• Examples
• Constraints
• Approach 1: Linear Search
• Approach 2: Binary Search (Iterative)
• Approach 3: Binary Search (Recursive)

Examples

Example 1:

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4

Example 2:

Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1

Constraints

1 <= nums.length <= 10⁴
-10⁴ < nums[i], target < 10⁴
All the integers in nums are unique.
nums is sorted in ascending order.

Linear Search

Intuition Iterate through the array element by element until the target is found or the end of the array is reached.

Steps

• Loop through the array from the first index to the last.
• Check if the current element equals the target.
• If found, return the index; otherwise, continue.
• If the loop finishes without finding the target, return -1.

from typing import List

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        for i in range(len(nums)):
            if nums[i] == target:
                return i
        return -1

Complexity

• Time: O(n)
• Space: O(1)
• Notes: Simple but inefficient for large sorted arrays compared to binary search.

Binary Search (Iterative)

Intuition Since the array is sorted, we can repeatedly divide the search interval in half. If the target is less than the middle element, search the left half; otherwise, search the right half.

Steps

• Initialize two pointers, left at 0 and right at the last index.
• While left is less than or equal to right:
  • Calculate the middle index mid.
  • If nums[mid] equals target, return mid.
  • If target is greater than nums[mid], move left to mid + 1.
  • If target is less than nums[mid], move right to mid - 1.
• If the loop ends, the target is not in the array, so return -1.

from typing import List

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

Complexity

• Time: O(log n)
• Space: O(1)
• Notes: Optimal approach for sorted arrays.

Binary Search (Recursive)

Intuition Implement the divide and conquer strategy recursively by defining a helper function that takes the current search boundaries.

Steps

• Define a recursive function that accepts left and right indices.
• Base case: if left > right, return -1.
• Calculate mid.
• If nums[mid] equals target, return mid.
• If target is less than nums[mid], recurse on the left half (right = mid - 1).
• If target is greater than nums[mid], recurse on the right half (left = mid + 1).

from typing import List

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        def binarySearch(left, right):
            if left > right:
                return -1
            mid = left + (right - left) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                return binarySearch(mid + 1, right)
            else:
                return binarySearch(left, mid - 1)
        
        return binarySearch(0, len(nums) - 1)

Complexity

• Time: O(log n)
• Space: O(log n)
• Notes: Uses stack space for recursion, which is slightly less memory efficient than the iterative approach.