Binary Search II in Python with O(log n) Time Complexity

Implement a recursive Binary Search algorithm that given a sorted array of integers nums, finds and returns the index of a given value.

If the value doesn't exist in nums, return -1.

Example 1:

Input: nums = [1, 2, 4, 5], value = 4
Output: 2
Explanation: nums[2] is 4

Note:

Your algorithm should run in O(log n) time and use O(log n) extra space.

Understanding the Problem

The core challenge of this problem is to efficiently find the index of a given value in a sorted array using a recursive approach. Binary search is a classic algorithm that divides the search interval in half repeatedly, making it highly efficient for sorted arrays.

Common applications of binary search include searching in databases, finding elements in sorted data structures, and solving algorithmic problems that require efficient search operations.

Potential pitfalls include not handling the base case correctly, which can lead to infinite recursion or incorrect results.

Approach

To solve this problem, we can use the following approach:

Define a recursive function binarySearch(nums, left, right) that searches for the value in the subarray nums[left...right].
Compute the middle index mid and compare nums[mid] to the target value.
If nums[mid] is equal to the value, return mid.
If nums[mid] is less than the value, search in the right subarray nums[mid + 1...right].
If nums[mid] is greater than the value, search in the left subarray nums[left...mid - 1].
If left exceeds right, return -1 as the value is not present in the array.

Algorithm

Here is a step-by-step breakdown of the algorithm:

Define the base case: if left > right, return -1.
Calculate the middle index: mid = left + (right - left) // 2.
Compare nums[mid] with the target value:
- If nums[mid] == value, return mid.
- If nums[mid] < value, recursively search in the right subarray.
- If nums[mid] > value, recursively search in the left subarray.

Code Implementation

def binary_search(nums, value):
    def helper(nums, left, right):
        # Base case: if left index exceeds right, value is not present
        if left > right:
            return -1
        
        # Calculate the middle index
        mid = left + (right - left) // 2
        
        # Check if the middle element is the target value
        if nums[mid] == value:
            return mid
        # If the middle element is less than the target, search in the right subarray
        elif nums[mid] < value:
            return helper(nums, mid + 1, right)
        # If the middle element is greater than the target, search in the left subarray
        else:
            return helper(nums, left, mid - 1)
    
    # Initial call to the helper function with the full array range
    return helper(nums, 0, len(nums) - 1)

# Example usage
nums = [1, 2, 4, 5]
value = 4
print(binary_search(nums, value))  # Output: 2

Complexity Analysis

The time complexity of the binary search algorithm is O(log n) because the search interval is halved in each recursive call. The space complexity is also O(log n) due to the recursive call stack.

Edge Cases

Potential edge cases include:

Empty array: The function should return -1.
Value not present in the array: The function should return -1.
Array with one element: The function should correctly identify if the single element is the target value or not.

Examples:

binary_search([], 4)  # Output: -1
binary_search([1], 1)  # Output: 0
binary_search([1], 2)  # Output: -1

Testing

To test the solution comprehensively, consider the following test cases:

Simple cases with small arrays.
Edge cases with empty arrays and single-element arrays.
Cases where the value is not present in the array.
Cases with large arrays to ensure efficiency.

Example test cases:

assert binary_search([1, 2, 4, 5], 4) == 2
assert binary_search([1, 2, 4, 5], 3) == -1
assert binary_search([], 4) == -1
assert binary_search([1], 1) == 0
assert binary_search([1], 2) == -1

Thinking and Problem-Solving Tips

When approaching such problems, consider the following tips:

Understand the problem requirements and constraints thoroughly.
Break down the problem into smaller subproblems and solve them recursively.
Think about the base case and how to handle it correctly.
Practice solving similar problems to improve your problem-solving skills.

Conclusion

In this blog post, we discussed the recursive binary search algorithm, its implementation in Python, and its complexity analysis. Understanding and solving such problems is crucial for efficient searching in sorted data structures. Practice and explore further to enhance your problem-solving skills.

Additional Resources

For further reading and practice problems, consider the following resources: