Binary Search easy

Problem Statement

Given a sorted (in ascending order) integer array nums of n integers and a target integer, 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:

1. Initialization: Set left pointer to 0 and right pointer to nums.length - 1.
2. Iteration: While left is less than or equal to right:
   • Calculate the middle index: middle = Math.floor((left + right) / 2). Avoid (left + right) / 2 to prevent potential integer overflow with very large arrays.
   • Comparison:
     • If nums[middle] equals target, return middle.
     • If nums[middle] is less than target, move the left pointer to middle + 1 (search in the right half).
     • If nums[middle] is greater than target, move the right pointer to middle - 1 (search in the left half).
3. Target Not Found: If the loop completes without finding the target, return -1.

Explanation:

The algorithm employs Binary Search, a highly efficient searching technique for sorted data. It works by repeatedly dividing the search interval in half. By comparing the middle element with the target, we can eliminate half of the remaining search space in each iteration. This results in a logarithmic time complexity, making it much faster than linear search for large datasets.

Code:

function search(nums: number[], target: number): number {
    let left = 0;
    let right = nums.length - 1;

    while (left <= right) {
        const middle = Math.floor((left + right) / 2);

        if (nums[middle] === target) {
            return middle;
        } else if (nums[middle] < target) {
            left = middle + 1;
        } else {
            right = middle - 1;
        }
    }

    return -1; 
};

Complexity:

• Time Complexity: O(log n) - Binary search halves the search space with each comparison.
• Space Complexity: O(1) - The algorithm uses a constant amount of extra space regardless of the input size. It's an in-place algorithm.