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 and Explanation:

The problem requires implementing a binary search algorithm. Binary search is an efficient algorithm for finding a target value within a sorted array. It works by repeatedly dividing the search interval in half. If the target value is less than the middle element, the search continues in the lower half; otherwise, it continues in the upper half. This process continues until the target value is found or the search interval is empty.

Here's a breakdown of the steps:

1. Initialization: Set left pointer to 0 (start of the array) and right pointer to nums.length - 1 (end of the array).

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

   • Calculate the mid point: mid = left + (right - left) / 2. This prevents potential integer overflow.
   • Compare nums[mid] with target:
     • If nums[mid] == target, the target is found, return mid.
     • If nums[mid] < target, the target is in the right half, so update left = mid + 1.
     • If nums[mid] > target, the target is in the left half, so update right = mid - 1.

3. Target Not Found: If the loop completes without finding the target, it means the target is not in the array. Return -1.

Code (Java):

class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return -1; // Target not found
    }
}

Complexity:

• Time Complexity: O(log n) - Binary search reduces the search space by half in each iteration.
• Space Complexity: O(1) - The algorithm uses a constant amount of extra space regardless of the input size.