LeetCode: 704 Binary Search

Given a sorted (in ascending order) integer array nums of n elements and a target value target, write a function to search target in nums. If target exists, then return its index, otherwise, return -1.

Example:

Input: nums = [-1, 0, 3, 5, 9, 12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4

问题

给定一个按升序排序的整数数组 nums 和一个目标值 target，编写一个函数在 nums 中搜索 target。如果 target 存在，则返回其索引，否则返回 -1。

解决方案 1

迭代二分查找方法

Approach 1 / 方法 1

This solution uses the iterative binary search technique. The idea is to repeatedly divide the search interval in half until the target value is found or the interval is empty.

该解决方案使用迭代二分查找技术。其思想是反复将搜索区间减半，直到找到目标值或区间为空。

Implementation / 实现

python

# Solution 1 implementation in Python
def binarySearch(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

Explanation / 解释

1. Step 1 / 第一步:

• Initialize left to 0 and right to the length of nums minus 1.
  将 left 初始化为 0，将 right 初始化为 nums 的长度减去 1。

2. Step 2 / 第二步:

• While left is less than or equal to right, repeat the following steps:
  当 left 小于等于 right 时，重复以下步骤：

  • Compute the middle index mid.
    计算中间索引 mid。

  • If nums[mid] is equal to target, return mid.
    如果 nums[mid] 等于 target，返回 mid。

  • If nums[mid] is less than target, set left to mid + 1.
    如果 nums[mid] 小于 target，将 left 设为 mid + 1。

  • If nums[mid] is greater than target, set right to mid - 1.
    如果 nums[mid] 大于 target，将 right 设为 mid - 1。

3. Step 3 / 第三步:

• If the loop ends without finding the target, return -1.
  如果循环结束时没有找到目标值，返回 -1。

Complexity Analysis / 复杂度分析

• Time Complexity: O(log n), where n is the number of elements in the array.
  时间复杂度: O(log n)，其中n是数组中的元素数量。

• Space Complexity: O(1), since we are using a fixed amount of additional space.
  空间复杂度: O(1)，因为我们使用了固定数量的额外空间。

Key Concept / 关键概念

• Binary search technique to efficiently locate a target value in a sorted array.
  使用二分查找技术高效定位排序数组中的目标值。

解决方案 2

递归二分查找方法

Approach 2 / 方法 2

This solution uses the recursive binary search technique. The idea is similar to the iterative method but uses a recursive function to divide the search interval in half.

该解决方案使用递归二分查找技术。其思想类似于迭代方法，但使用递归函数将搜索区间减半。

Implementation / 实现

python

# Solution 2 implementation in Python
def binarySearch(nums, target):
    return binarySearchHelper(nums, target, 0, len(nums) - 1)

def binarySearchHelper(nums, target, left, right):
    if left > right:
        return -1
    mid = left + (right - left) // 2
    if nums[mid] == target:
        return mid
    elif nums[mid] < target:
        return binarySearchHelper(nums, target, mid + 1, right)
    else:
        return binarySearchHelper(nums, target, left, mid - 1)

Explanation / 解释

1. Step 1 / 第一步:

• Define a helper function binarySearchHelper with parameters nums, target, left, and right.
  定义一个辅助函数 binarySearchHelper，参数为 nums、target、left 和 right。

2. Step 2 / 第二步:

• If left is greater than right, return -1.
  如果 left 大于 right，返回 -1。

3. Step 3 / 第三步:

• Compute the middle index mid.
  计算中间索引 mid。

4. Step 4 / 第四步:

• If nums[mid] is equal to target, return mid.
  如果 nums[mid] 等于 target，返回 mid。

5. Step 5 / 第五步:

• If nums[mid] is less than target, recursively call binarySearchHelper with mid + 1 and right.
  如果 nums[mid] 小于 target，用 mid + 1 和 right 递归调用 binarySearchHelper。

6. Step 6 / 第六步:

• If nums[mid] is greater than target, recursively call binarySearchHelper with left and mid - 1.
  如果 nums[mid] 大于 target，用 left 和 mid - 1 递归调用 binarySearchHelper。

Complexity Analysis / 复杂度分析

• Time Complexity: O(log n), where n is the number of elements in the array.
  时间复杂度: O(log n)，其中n是数组中的元素数量。

• Space Complexity: O(log n), due to the recursion stack.
  空间复杂度: O(log n)，由于递归调用栈。

Key Concept / 关键概念

• Recursive binary search technique to locate a target value in a sorted array.
  使用递归二分查找技术定位排序数组中的目标值。

Comparison / 比较

Comparison Between All Approaches

1. Algorithm:

   • Approach 1 (Iterative Binary Search):

     • Uses a loop to divide the search interval in half iteratively.

   • Approach 2 (Recursive Binary Search):

     • Uses a recursive function to divide the search interval in half.

2. Efficiency:

   • Time Complexity:

     • Both approaches have a time complexity of O(log n), where n is the number of elements in the array.

   • Space Complexity:

     • The iterative method has a space complexity of O(1).
     • The recursive method has a space complexity of O(log n) due to the recursion stack.

3. Readability and Maintainability:

   • Approach 1 (Iterative Binary Search):

     • Simple and uses minimal space, making it easier to understand and maintain.

   • Approach 2 (Recursive Binary Search):

     • Clear and concise but involves recursion, which can lead to stack overflow for very large arrays.

4. Best Practice:

   • Recommended Solution: Approach 1 (Iterative Binary Search):
     • Reason: Approach 1 is preferred due to its simplicity, efficiency, and minimal space usage. It avoids the risk of stack overflow associated with recursion.

Summary / 总结

• Use Approach 1 for a simple, efficient, and space-saving solution.
• Approach 1’s iterative nature makes it easier to follow and implement.

Tips / 提示

• Ensure the array is sorted before applying binary search.
• Handle edge cases such as an empty array or target not present in the array.

Solution Template for similar questions / 提示

• Use binary search techniques for efficient searching in sorted arrays.
• Implement both iterative and recursive approaches as needed.

What does the main algorithm of this question aim to test? / 这个问题的主要算法旨在测试什么？

Understanding of binary search techniques and their application in searching sorted arrays.

5 more similar questions / 推荐5问题

1. LeetCode 33. Search in Rotated Sorted Array
2. LeetCode 74. Search a 2D Matrix
3. LeetCode 34. Find First and Last Position of Element in Sorted Array

Recommend Resources:

Binary Search – Leetcode 704 – Python NeetCode