直接二分:
left和right先skip掉相同的数,
然后left, right取mid,看mid的左[mid-1]右[mid+1]:
如果左右都小,则找到;
如果左小右大,则在非递减部分,更新left=mid+1
如果左大右小,则在非递增部分,更新right=mid-1
贴个js代码不知道有没有bug,有的话麻烦提一下:
function turnPoint(a) {
var left = 0,
right = a.length - 1,
mid,
len = a.length;
while (left <= right) {
while (left <= right && a[left + 1] == a[left]) left++;
while (left <= right && a[right - 1] == a[right]) right--;
mid = (left + right) / 2;
if (mid > 0 && mid + 1 < len) {
if (a[mid - 1] < a[mid] && a[mid + 1] < a[mid])
return a[mid];
else if (a[mid - 1] < a[mid] && a[mid] < a[mid + 1])
left = mid + 1;
else if (a[mid - 1] > a[mid] && a[mid] > a[mid + 1])
right = mid - 1;
}
}
return -1;
}
console.log(turnPoint([1,2,3,4,5,4,3,2,1]));
console.log(turnPoint([1,1,1,1,1,2,1,1]));
console.log(turnPoint([1,2,1,1,1,1,1,1]));