algoadvance

  1. Binary Search

Given a sorted array of n integers and a target value, write a function to search for the target in the array. If the 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

Clarifying Questions

  1. Are the elements in the array guaranteed to be in ascending order?
    • Yes, the array is sorted in ascending order.
  2. What should be returned if the target value appears multiple times in the array?
    • The problem statement implies to return the index of any occurrence of the target, but since it’s a sorted array, usually the first occurrence found will be returned.
  3. Can the array contain negative numbers?
    • Yes, the array can contain negative numbers as illustrated in the examples.
  4. What is the maximum size of the array?
    • While the problem statement does not explicitly state a maximum size, typically constraints will be provided in the associated online judge problem. For simplicity, we can assume the array size to be within a practical limit.

Strategy

To achieve the required O(log n) runtime complexity, the solution should use the binary search algorithm. Binary search works as follows:

  1. Initialize two pointers, left starting at index 0 and right starting at the last index of the array.
  2. Calculate the mid index.
  3. Compare the element at the mid index with the target.
    • If the element at mid is the target, return mid.
    • If the target is less than the element at mid, adjust the right pointer to mid - 1.
    • If the target is greater than the element at mid, adjust the left pointer to mid + 1.
  4. Repeat the process until left exceeds right.

Code

Here is the Python implementation of the binary search algorithm:

def search(nums, target):
    left, right = 0, len(nums) - 1
    
    while left <= right:
        mid = left + (right - left) // 2
        
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return -1

Time Complexity

The time complexity of the binary search algorithm is O(log n), as each iteration of the loop halves the search space. This meets the problem’s requirement for an efficient search.

Explanation with an Example

Let’s go through the example nums = [-1,0,3,5,9,12], target = 9:

  1. Initially, left=0, right=5 (last index), mid = 2 (nums[2] = 3), target = 9.
  2. Since 3 < 9, update left = 3.
  3. Now, left=3, right=5, mid = 4 (nums[4] = 9).
  4. 9 matches the target, so return 4.

With this approach, the function successfully returns the index of the target value if it exists, or -1 if it doesn’t.

Try our interview co-pilot at AlgoAdvance.com