chen.tso
BAN USER@SycophantEve
Let me see if I got this right.
When you do a binary search, you might not find it, so you split up left and right on where your failed binary search is. At this point, if you look at the last two values of the left subarray and first two values of the right sub array, you can figure out which side the peak is on.
In your example. 1,4,5 means the left subarray is increasing which means peak is in the right sub array.
Now when you do the binary search on the right sub array, we can do a modified binary search in that we know there's a peak and two sides but only one side will have possible search because the other side is already bounded when we did the left/right subarray split. So your example 7, 10, 11, 9, 6, -1 ... peak is at 11, but we know the 6 must be on the right side of the peak because when we cut the array in two previously, we know the left side is already greater than 6. So you do a binary search... if the mid value is greater than 6 you binary search right, if a mid value is less than 6 you binary search left (reverse)
Did I get the gist of thing?
- chen.tso June 24, 2015