Can You Apply Binary Search on an Unsorted Array? Let’s Explore LeetCode 162 (Find Peak Element)

Introduction

Binary search is a powerful algorithm typically used on sorted arrays to efficiently locate elements. However, a common question arises: Can binary search be applied to an unsorted array? The answer is nuanced and can depend on the specific problem constraints. In this blog post, we will explore this concept through LeetCode Problem 162: “Find Peak Element.”

Understanding the Problem

LeetCode 162 asks us to find a peak element in an array. An element is considered a peak if it is greater than or equal to its neighbors. For edge elements, they only need to be greater than or equal to their single neighbor. The challenge is to find a peak with a time complexity of O(log n), hinting at the potential use of binary search.

Problem Statement

Given an integer array nums, you need to find a peak element and return its index. The array can have multiple peaks, and you are free to return any of the peak indices.

Key Observations

1. Local vs Global Peaks: The problem allows for multiple valid answers. A peak does not need to be the highest element overall but just a local maximum.

2. Binary Search Approach: The essence of applying binary search here lies in the fact that if you are at a position mid in the array:

   • If nums[mid] is less than nums[mid + 1], then a peak must exist in the right half (including mid + 1).
   • If nums[mid] is less than nums[mid - 1], then a peak must exist in the left half (including mid - 1).
   • If nums[mid] is greater than both neighbors, then you have found a peak.

The Optimal Approach

Algorithm

1. Initialize two pointers, left and right, at the start and end of the array.
2. Use a while loop to perform binary search until left is less than or equal to right.
3. Calculate mid as the average of left and right.
4. Check the conditions mentioned above to adjust left or right accordingly.
5. If you find a peak, return its index.

Time Complexity

The time complexity of this algorithm is O(log n) due to the halving of the search space at each step, which is optimal for this problem.

Space Complexity

The space complexity is O(1) because we are using only a constant amount of additional space (for pointers and indices).

Edge Cases

• Arrays of length 1 are trivially a peak.
• Arrays with all elements the same will also yield a valid peak.
• Care should be taken for boundary checks to avoid accessing out-of-bounds indices.

Conclusion

While binary search is primarily associated with sorted arrays, we see that it can also be effectively applied to unsorted arrays under certain conditions. In the case of LeetCode 162, we leveraged the properties of local peaks to guide our search, demonstrating the versatility of binary search beyond its conventional limitations.

Further Discussion

• What other problems can we explore where binary search might be applied in non-traditional ways?
• How does this approach compare with brute-force solutions in terms of performance?

Feel free to share your thoughts or insights on the application of binary search in various contexts!

Related Posts

• Any good subs/pages for job postings or referrals (USA)