Intermediate Level
Implement the findPeakUsingBinarySearch method that returns a peak element index using binary search.
The input contains an integer array nums and its length size. Your task is to return the index of a peak element.
A peak element is greater than its adjacent elements. For boundary positions, only the existing neighbour is considered.
For example, in [1,2,3,1], the value 3 at index 2 is a peak because it is greater than both adjacent values.
Example 1
Input
nums (int[]) =
[1,2,3,1]size (int) =
4Returns (int)
2Example 2
Input
nums (int[]) =
[1,2,1,3,5,6,4]size (int) =
7Returns (int)
5Example 3
Input
nums (int[]) =
[1]size (int) =
1Returns (int)
0Use binary search by comparing the middle value with its right neighbour.
If nums[mid] is less than nums[mid + 1], the array is rising at that point, so a peak must exist on the right side. Otherwise, a peak exists at mid or on the left side.
Continue until the search range becomes a single index. That index is a peak position.
Pseudocode:
function findPeakUsingBinarySearch(nums, size):
left = 0
right = size - 1
while left < right:
mid = left + (right - left) / 2
if nums[mid] < nums[mid + 1]:
left = mid + 1
else:
right = mid
return leftReady to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run