704. Binary Search Easy

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.

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

Approach

Input: An ascending sorted array nums, a target value target

Output: Return the index of the target value in the array, if not exists return -1

This problem belongs to the Basic Search category, suitable for using binary search to quickly locate the target value in an ordered array.

We shrink the search interval continuously through binary search. The specific steps are as follows:

Initialize the left and right boundaries: left = 0, right = len(nums) - 1

Loop the following logic until left > right:

Calculate the middle position mid = (left + right) // 2

• If nums[mid] == target, it means we found the target, directly return mid.
• If nums[mid] < target, it means the target value is in the right half, update left = mid + 1.
• If nums[mid] > target, it means the target value is in the left half, update right = mid - 1.

If the loop ends and the target value is still not found, it means it doesn't exist, return -1.

Implementation

python

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        # Initialize the left and right pointers, pointing to the beginning and end of the array respectively
        left, right = 0, len(nums) - 1

        # Continue the loop while the search interval is not empty
        while left <= right:
            # Calculate the middle position, avoiding integer overflow
            mid = left + (right - left) // 2

            if nums[mid] == target:
                # Found the target value, directly return the index
                return mid
            elif nums[mid] < target:
                # The middle value is less than the target, meaning the target is in the right half
                left = mid + 1
            else:
                # The middle value is greater than the target, meaning the target is in the left half
                right = mid - 1

        # If the loop ends without finding it, return -1 indicating it doesn't exist
        return -1

javascript

const search = function(nums, target) {
    // Initialize the left and right pointers, pointing to the beginning and end of the array
    let left = 0;
    let right = nums.length - 1;

    // Continue searching while the left pointer is less than or equal to the right pointer
    while (left <= right) {
        // Calculate the middle position, avoiding overflow
        const mid = Math.floor(left + (right - left) / 2);

        if (nums[mid] == target) {
            // Found the target value, return the index directly
            return mid;
        } else if (nums[mid] < target) {
            // The middle value is less than the target, target is on the right, move left pointer right
            left = mid + 1;
        } else {
            // The middle value is greater than the target, target is on the left, move right pointer left
            right = mid - 1;
        }
    }

    // Target value not found, return -1
    return -1;
};

Complexity Analysis

• Time Complexity: O(log n)
• Space Complexity: O(1)

Links

704. Binary Search (English)

704. 二分查找 (Chinese)