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 to Solve:

1. Initialization: Define two pointers, left and right, pointing to the beginning and end of the array respectively.
2. Iteration: While left is less than or equal to right:
   • Calculate the middle index mid = (left + right) / 2. Note: Using (left + right) / 2 can lead to integer overflow for very large arrays. A safer alternative is left + (right - left) / 2.
   • Compare nums[mid] with target:
     • If nums[mid] == target, return mid.
     • If nums[mid] < target, update left = mid + 1 (search in the right half).
     • If nums[mid] > target, update right = mid - 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. 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 halving process continues until the target is found or the search interval is empty. The logarithmic time complexity arises because the size of the search interval is halved with each iteration.

Code (C#):

public 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; // Safer way to calculate mid

            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 halves the search space with each comparison.
• Space Complexity: O(1) - Constant extra space is used, regardless of the input size. The algorithm operates in place.