Suppose we are given an array A[1 .. n] with the special property that A[1] ≥ A[2] and
A[n ? 1] ≤ A[n]. We say that an element A[x] is a local minimum if it is less than or equal
to both its neighbors, or more formally, if A[x ? 1] ≥ A[x] and A[x] ≤ A[x + 1]. For example,
there are ?ve local minima in the following array:
9 7 7 2 1 3 7 5 4 7 3 3 4 8 6 9
We can obviously ?nd a local minimum in O(n) time by scanning through the array. Describe

and analyze an algorithm that ?nds a local minimum in O(log n) time

bool GetPivot(int a[], int n, int& res) {assert(a && n > 0);int nBeg = 0;int nEnd = n - 1;while (nBeg + 2 <= nEnd){int nMid = (nBeg + nEnd)/2;if (a[nMid - 1] >= a[nMid] && a[nMid] <= a[nMid + 1]){res = a[nMid];return false;}else if (a[nMid - 1] >= a[nMid] && a[nMid] > a[nMid + 1])nBeg = nMid + 1;elsenEnd = nMid - 1;}return false; }
有些題目不難，主要是要深入分析

總結(jié)

以上是生活随笔為你收集整理的找数组波谷的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。