Practice/Google/Leetcode 704. Binary Search

Leetcode 704. Binary Search

CodingMust

Problem

You are given an array of integers sorted in ascending order, where all elements are distinct. Your task is to find the position (index) of a specific target value within this array.

If the target value exists in the array, return its index. If the target value is not present, return -1.

Your algorithm must achieve O(log n) runtime complexity, where n is the length of the array.

Requirements

1. Implement an efficient search algorithm that runs in logarithmic time
2. Return the zero-based index if the target is found
3. Return -1 if the target does not exist in the array
4. Do not use built-in search methods that would trivialize the problem

Constraints

• 1 ≤ nums.length ≤ 104
• -104 < nums[i], target < 104
• All integers in nums are unique
• nums is sorted in ascending order
• Must run in O(log n) time complexity

Examples

Example 1:

Input: nums = [-1, 0, 3, 5, 9, 12], target = 9 Output: 4 Explanation: The value 9 appears at index 4 in the array

Example 2:

Input: nums = [-1, 0, 3, 5, 9, 12], target = 2 Output: -1 Explanation: The value 2 does not exist in the array

Example 3:

Input: nums = [5], target = 5 Output: 0 Explanation: Single element array where the target matches