Giả sử chúng ta phải tìm phần tử đỉnh trong một mảng. Phần tử đỉnh là phần tử lớn hơn các hàng xóm của nó. Giả sử mảng đầu vào nums, với nums[i] ≠ nums[i+1], tìm một phần tử đỉnh và trả về chỉ số của nó. Mảng có thể có nhiều phần tử đỉnh, trong trường hợp đó trả về chỉ số của bất kỳ phần tử đỉnh nào. Ta có thể tưởng tượng nums[-1] = nums[n] = -∞. Ví dụ, nếu mảng là [1,2,1,3,5,6,4], các phần tử đỉnh là chỉ số 1 hoặc 5.
Để giải quyết, chúng ta sử dụng tìm kiếm nhị phân:
low := 0, high := chỉ số cuối cùng của mảng.
Khi low < high:
- mid := low + (high - low + 1) // 2.
- Nếu mid - 1 >= 0 và nums[mid-1] <= nums[mid], thì low = mid, ngược lại high = mid - 1.
Trả về nums[low] (hoặc low tùy yêu cầu).
Ví dụ
class Solution(object):
def findPeakElement(self, nums):
low = 0
high = len(nums) - 1
while low < high:
mid = low + (high - low + 1) // 2
if (mid - 1 >= 0 and nums[mid-1] <= nums[mid]):
low = mid
else:
high = mid - 1
return nums[low]
ob1 = Solution()
print(ob1.findPeakElement([15,35,85,96,5,6,8,12]))
Đầu vào
[15,35,85,96,5,6,8,12]
Đầu ra
96