Binary Search easy

Problem Statement

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

Steps to Solve:

Binary Search is an efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing in half the portion of the list that could contain the item, until you've narrowed down the possible locations to just one.

1. Initialization: Set left pointer to 0 and right pointer to the length of the array minus 1.

2. Iteration: While left is less than or equal to right:

   • Calculate the middle index: middle = (left + right) // 2. Using // ensures integer division.
   • Compare the element at nums[middle] with the target:
     • If nums[middle] == target, return middle.
     • If nums[middle] < target, the target must be in the right half, so update left = middle + 1.
     • If nums[middle] > target, the target must be in the left half, so update right = middle - 1.

3. Target Not Found: If the loop completes without finding the target, return -1.

Explanation:

The algorithm leverages the sorted nature of the input array. By repeatedly halving the search space, it achieves logarithmic time complexity. The key is that each comparison eliminates roughly half of the remaining possibilities.

Code (Python):

def search(nums, target):
    """
    Searches for a target value in a sorted array using binary search.

    Args:
        nums: A sorted list of integers.
        target: The integer to search for.

    Returns:
        The index of the target if found, otherwise -1.
    """
    left = 0
    right = len(nums) - 1

    while left <= right:
        middle = (left + right) // 2
        if nums[middle] == target:
            return middle
        elif nums[middle] < target:
            left = middle + 1
        else:
            right = middle - 1

    return -1

Complexity:

• Time Complexity: O(log n), where n is the length of the input array. This is because the search space is halved in each iteration.
• Space Complexity: O(1). The algorithm uses a constant amount of extra space regardless of the input size. It's an in-place algorithm.