leetcode 33 解法求解释

2021-07-02 01:35:16 +08:00
 xiaoming1992

题目: 33. Search in Rotated Sorted Array 一个很清晰简洁的解法: Clever idea making it simple

int search(vector<int>& nums, int target) {
    int lo = 0, hi = nums.size();
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        
        double num = (nums[mid] < nums[0]) == (target < nums[0])
                   ? nums[mid]
                   : target < nums[0] ? -INFINITY : INFINITY;
                   
        if (num < target)
            lo = mid + 1;
        else if (num > target)
            // 这儿为什么不能 -1 ?
            hi = mid;
        else
            return mid;
    }
    return -1;
}

这个解法省了我几万个脑细胞, lo = mid + 1 很好理解, 但是 hi = mid - 1 为什么出错, 我想破脑袋都没想明白...

2226 次点击
所在节点    LeetCode
4 条回复
lostvincent
2021-07-02 10:09:15 +08:00
int mid = ( lo + hi ) / 2 这步,其实是 floor( ( lo + hi ) / 2 )
如果 lo = mid + 1 的话,lo 正好是 target,那么 hi 会递减到 lo + 1 为止,然后 下一步 ( lo + hi ) / 2 就是 lo
如果 hi = mid - 1 这步执行之后,hi 正好是 target,那他就永远找不到了,因为 lo 递增到 hi - 1 之后,( lo + hi ) / 2 还是 lo

你可以试试 nums = [1, 2, 3, 4, 5] target = 2
lostvincent
2021-07-02 10:11:25 +08:00
上一楼写错 case 了,当成找不大于不小于到了,抱歉
lostvincent
2021-07-02 10:21:34 +08:00
他这里是 while lo < hi, hi = mid - 1 之后,如果 hi == lo,就不会进 while,这时候如果 nums[lo] == target,那么结果就会变成 -1
更正 case:nums = [4,5,6,7,0,1,2] target = 0
xiaoming1992
2021-07-02 12:14:21 +08:00
@lostvincent 非常感谢!这个题目昨晚卡了我很久,一直想不通 high - 1 和 low + 1 有什么区别,原来区别出在 floor 这儿,感谢感谢!

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/787031

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX