Algorithms 101: Binary Search Doesn’t Have to Occur in a Sorted Array

二分搜索不一定发生在有序数组上

In computer science, binary search is an efficient algorithm used to find a specific element in a sorted array. However, binary search is not limited to only sorted arrays. It can also be applied in specific scenarios where the array is not entirely ordered but still has certain properties that allow binary search to be effective, such as in the problem of finding a peak element.

在计算机科学中，二分搜索是一种用于在有序数组中查找特定元素的高效算法。然而，二分搜索并不仅限于有序数组。在某些特定情况下，即使数组不是完全有序的，但仍然具有某些属性使得二分搜索仍然有效，比如在查找峰值元素的问题中。

1. Problem Description

问题描述

Problem Background

问题背景

In the array nums, a peak element is an element that is strictly greater than its neighboring elements. Given an integer array nums, where every adjacent pair of elements is unique, you need to find a peak element and return its index. The array may contain multiple peaks, and in that case, you can return the index of any of the peaks.

在数组 nums 中，峰值元素是指其值严格大于相邻元素的元素。给定一个整数数组 nums，其中每对相邻元素都不同，你需要找到一个峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，你可以返回任何一个峰值的索引。

You can assume that nums[-1] = nums[n] = -∞, where n is the length of the array.

你可以假设 nums[-1] = nums[n] = -∞，其中 n 是数组的长度。

Examples

示例

Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element, and your function should return the index 2.

输入: nums = [1,2,3,1]
输出: 2
解释: 3 是峰值元素，你的函数应该返回索引 2。

Input: nums = [1,2,1,3,5,6,4]
Output: 1 or 5 
Explanation: Your function can return index 1 where the peak element is 2, or index 5 where the peak element is 6.

输入: nums = [1,2,1,3,5,6,4]
输出: 1 或 5 
解释: 你的函数可以返回索引 1，其峰值元素为 2；或者返回索引 5，其峰值元素为 6。

Constraints

约束条件

• The number of elements in nums is between 1 and 1000.

• Any two adjacent elements in nums are not equal.

• nums 中的元素数量为 1 到 1000 之间。

• 数组 nums 中的任何两个相邻元素都不相等。

2. Algorithm Analysis

算法分析

To meet the requirement of O(log n) time complexity, we can use the idea of binary search to solve this problem. Even though the array is not entirely sorted, we can determine the peak element’s location by comparing the middle element with its adjacent elements and narrowing down the search range accordingly.

为了满足 O(log n) 时间复杂度的要求，我们可以利用二分搜索的思想来解决这个问题。尽管数组不是完全有序的，但通过比较中间元素与其相邻元素的大小关系，我们可以确定峰值元素的位置，并据此缩小搜索范围。

Core Idea

核心思路

1. Initialize the search range as the entire array, i.e., left = 0, right = len(nums) - 1.

2. Calculate the middle index mid = (left + right) // 2.

3. Compare nums[mid] with nums[mid + 1]:

   • If nums[mid] > nums[mid + 1], then the peak is at mid or on the left side, so adjust right = mid.
   • Otherwise, the peak is on the right side, so adjust left = mid + 1.

4. Repeat the above steps until left == right. At this point, left is the index of the peak element.

5. 初始化搜索区间为整个数组，即 left = 0, right = len(nums) - 1。

6. 计算中间索引 mid = (left + right) // 2。

7. 比较 nums[mid] 与 nums[mid + 1]：

   • 如果 nums[mid] > nums[mid + 1]，则峰值在 mid 或 mid 左侧，因此调整 right = mid。
   • 否则，峰值在 mid 右侧，因此调整 left = mid + 1。

8. 重复上述步骤，直到 left == right。此时，left 即为峰值元素的索引。

Code Implementation

代码实现

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

Detailed Explanation

详细解释

• Initial State: left and right point to the two ends of the array.

• Middle Element Check: By comparing the middle element nums[mid] with nums[mid + 1], we can determine whether the peak is on the left or right side of mid.

• Iteration: The search range is gradually narrowed based on the comparison, and eventually, left and right converge to the same position, which is the index of the peak element.

• Return Result: Return left, which is the index of the peak element.

• 初始状态：left 和 right 分别指向数组的左右两端。

• 中间元素判断：通过比较中间元素 nums[mid] 与 nums[mid + 1]，我们可以确定峰值元素是在 mid 的左侧还是右侧。

• 迭代过程：根据比较结果，逐步缩小搜索范围，最终 left 和 right 会收敛到同一个位置，该位置即为峰值元素的索引。

• 返回结果：返回 left，即峰值元素的索引。

Time Complexity Analysis

时间复杂度分析

Since this algorithm narrows the search range by half in each iteration, the overall time complexity is O(log n), which meets the problem’s requirement.

该算法在每次迭代中将搜索范围缩小一半，因此总的时间复杂度为 O(log n)，满足题目要求。

3. Conclusion

结论

By utilizing the concept of binary search, we can efficiently find a peak element in O(log n) time complexity. This method is not only applicable to sorted arrays but also to unsorted arrays that meet specific conditions, such as this peak element problem. In practice, understanding and mastering this variant of binary search is crucial for solving similar problems.

通过利用二分搜索的概念，我们可以在 O(log n) 时间复杂度内高效地找到数组中的峰值元素。这种方法不仅适用于有序数组，也适用于满足特定条件的无序数组，如本次的峰值元素问题。在实践中，理解和掌握这种二分搜索的变体应用对于解决类似的问题非常重要。

Test Link

测试链接

LeetCode 162: Find Peak Element