algoadvance

Leetcode 704. Binary Search

Problem Statement

Given a sorted array of integers nums and an integer target, write a function to search for 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

Constraints:

Clarifying Questions

  1. Is the input array always sorted in ascending order?
    • Yes, the prompt specifies that the array is sorted in ascending order.
  2. Are there any duplicate elements in the array?
    • No, all elements in nums are unique.
  3. What should the function return if the target is not found?
    • The function should return -1 if the target is not found.

Strategy

The problem requires an O(log n) runtime complexity, which is a strong indication to use the Binary Search algorithm. Here’s how the binary search will work in this context:

  1. Initialize two pointers, left and right, to represent the search interval’s boundaries.
    • left initially pointing to the first index (0).
    • right initially pointing to the last index (nums.length - 1).
  2. While the search interval is valid (i.e., left is less than or equal to right):
    • Compute the midpoint index mid as (left + right) / 2.
    • Compare the element at mid with the target:
      • If nums[mid] equals target, return mid.
      • If nums[mid] is less than target, move the left pointer to mid + 1 (search in the right subarray).
      • If nums[mid] is greater than target, move the right pointer to mid - 1 (search in the left subarray).
  3. If the loop ends without finding the target, return -1.

Code

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; // prevents overflow more safely than (left + right) / 2
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return -1; // Target not found
    }
}

Time Complexity

The time complexity of the binary search algorithm is O(log n) due to the following:

The space complexity is O(1) as we are only using a constant amount of extra space for variables left, right, and mid.

This completes the explanation and solution for the binary search algorithm in Java to solve the given problem on LeetCode.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI