Domain 1EasyCORE

Binary Search

The problem requires us to search for a target integer in a sorted array of integers using binary search. The inputs are: - `nums`: An array of integers sorted in ascending order. - `target`: An integer that we need to find in the array.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Binary Search

704. Binary Search

Model: qwen2.5-coder:14b
Topics: Binary Search
FAANG asked: 1
Acceptance rate: 54.3%


Problem Breakdown

The problem requires us to search for a target integer in a sorted array of integers using binary search. The inputs are:

  • nums: An array of integers sorted in ascending order.
  • target: An integer that we need to find in the array.

The output is:

  • The index of the target if it exists in the array.
  • -1 if the target does not exist in the array.

Implicit constraints and edge cases include:

  • The array can be empty, in which case the function should return -1.
  • All integers in the array are unique.
  • The array length is between 1 and 10^4.
  • The values of the integers range from -9999 to 9999.

Intuition

A brute-force approach would involve iterating through the entire array linearly to find the target, which would result in a time complexity of O(n). This is inefficient for large arrays. The key insight is that since the array is sorted, we can use binary search to reduce the time complexity to O(log n).

Binary search works by repeatedly dividing the search interval in half. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise, narrow it to the upper half. Repeatedly check until the value is found or the interval is empty.

Approach

We will implement a binary search algorithm using two pointers: left and right, which represent the current search bounds within the array. The steps are as follows:

  1. Initialize left to 0 and right to the last index of the array.
  2. While left is less than or equal to right:
    • Calculate the middle index mid as (left + right) // 2.
    • If nums[mid] equals the target, return mid.
    • If nums[mid] is less than the target, move the left pointer to mid + 1.
    • If nums[mid] is greater than the target, move the right pointer to mid - 1.
  3. If the loop exits without finding the target, return -1.

Complexity Analysis

  • Time Complexity: O(log n) because we are dividing the search space in half with each iteration.
  • Space Complexity: O(1) because we are using a constant amount of extra space.

Solution

def binary_search(nums, target):
    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

Edge Cases Handled

  • Empty Array: If the array is empty, left will be greater than right initially, and the function will return -1.
  • Target at Boundaries: The algorithm correctly handles cases where the target is the first or last element in the array.
  • Target Not Present: If the target is not present, the loop will exhaust all possibilities, and the function will return -1.