package main /** * * @param rotateArray int整型一维数组 * @return int整型 */ func minNumberInRotateArray( rotateArray []int ) int { // write code here left, right := 0, len(rotateArray)-1 for left < right { middle := left + (right - left)>>1 //如果中间值大于最右边的值,说明旋转之后最小的 //数字肯定在mid的右边,比如[3, 4, 5, 6, 7, 1, 2] if rotateArray[middle] > rotateArray[right] { left = middle + 1 }else if rotateArray[middle] < rotateArray[right] { //如果中间值小于最右边的值,说明旋转之后最小的 //数字肯定在mid的前面,比如[6, 7, 1, 2, 3, 4, 5], //注意这里mid是不能减1的,比如[3,1,3],我们这里只是 //证明了numbers[mid]比numbers[right]小,但有可能 //numbers[mid]是最小的,所以我们不能把它给排除掉 right = middle }else { //如果中间值等于最后一个元素的值,我们是没法确定最小值是 // 在mid的前面还是后面,但我们可以缩小查找范围,让right // 减1,因为即使right指向的是最小值,但因为他的值和mid // 指向的一样,我们这里并没有排除mid,所以结果是不会有影响的。 //比如[3,1,3,3,3,3,3]和[3,3,3,3,3,1,3],中间的值 //等于最右边的值,但我们没法确定最小值是在左边还是右边 right-- } } // 不断的缩小查找范围,当查找范围的长度为1的时候返回,也就是left等于right的时候 return rotateArray[left] }