704. Binary Search

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

Thought Process

Binary search is a classic algorithm to find a target value within a sorted array in O(log n) time complexity. It works by repeatedly dividing the search interval in half:

1. Start with two pointers: one at the beginning (left) and one at the end (right) of the array.
2. Find the middle index (mid) of the current search range.
3. Compare the middle element nums[mid] with the target:
   • If equal, return mid as the index of the target.
   • If nums[mid] < target, discard the left half by setting left = mid + 1.
   • If nums[mid] > target, discard the right half by setting right = mid - 1.
4. Repeat until the left pointer exceeds the right pointer.
5. If no match is found, return -1.

Go:

func search(nums []int, target int) int {
    // Initialize left and right boundaries
    left := 0
    right := len(nums) - 1

    // Continue while the search space is valid
    for left <= right {
        // Calculate the middle index to avoid overflow
        mid := left + (right-left)>>1

        // Check if the middle element is the target
        if nums[mid] == target {
            return mid
        } else if nums[mid] < target {
            // Target is in the right half
            left = mid + 1
        } else {
            // Target is in the left half
            right = mid - 1
        }
    }

    // Target not found in the array
    return -1
}

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;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }
}

PHP:

class Solution {
    /**
     * @param Integer[] $nums
     * @param Integer $target
     * @return Integer
     */
    function search($nums, $target) {
        if (count($nums) == 0) {
            return -1;
        }
        $left = 0;
        $right = count($nums) - 1;
        while ($left <= $right) {
            $mid = floor(($left + $right) / 2);
            if ($nums[$mid] == $target) {
                return $mid;
            }
            if ($nums[$mid] > $target) {
                $right = $mid - 1;
            } else {
                $left = $mid + 1;
            }
        }
        return -1;
    }
}