题解 | #旋转数组的最小数字#

旋转数组的最小数字

http://www.nowcoder.com/practice/9f3231a991af4f55b95579b44b7a01ba

  • 《剑指Offer》中的答案太过繁琐
  • 该答案非常精简,但是内容很多,主要是各种场景非常的精巧
  • 二分查找终止条件
  • 二分查找时,中间值跟谁比的问题(基准值)
import java.util.ArrayList;
public class Solution {
    public int minNumberInRotateArray(int [] a) {
        if (a == null || a.length == 0) return 0;
        int l = 0, r = a.length -1, m = 0;
        while (l < r) { // 注意终止条件
            if (a[l] < a[r]) { // 最高优先级的场景
                return a[l];
            }
            m = l + ((r - l) >> 1); // 较规范的求二分中间下标的写法,避免溢出且使用位运算
            if (a[m] > a[r]) l = m + 1; // 能判断出来m位于左序列,此时左指针可以移动到m+1
            else if (a[m] < a[r]) r = m; // m位于右序列,由于a[m]可能是候选结果,因此r不能越过m
            else r--; // 逐步缩小问题空间
        }
        return a[l];
    }
}
全部评论

相关推荐

评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务