算法：寻找峰一行 [英] Algorithm: Find peak in a line

问题描述

由于 N 整数，排成一条线，显示出高效的算法，可以找到一个高峰。峰值是一个数字，是不超过两个数少它旁边（或所述一个数它旁边，如果它是在该行的末端。）

Given n integers, arranged in a line, show an efficient algorithm that can find one peak. A peak is a number that is not less than the two numbers next to it (or the one number next to it, if it's at the end of the line.)

推荐答案

这是 O（log n）的算法存在。我们采用分而治之。

An O(log n) algorithm exists. We use divide-and-conquer.

find_peak(lo,hi):
  mid = (lo+hi)/2
  if A[mid] >= A[mid-1], A[mid+1] return mid
  if A[mid] < A[mid-1] 
    return find_peak(lo,mid-1) // a peak must exists in A[1..mid-1]
  if A[mid] < A[mid+1]
    return find_peak(mid+1,hi) // a peak must exists in A[mid+1..hi]

这篇关于算法：寻找峰一行的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！