这是一个创建于 1225 天前的主题，其中的信息可能已经有所发展或是发生改变。
题目: 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 为什么出错, 我想破脑袋都没想明白...
 |
1
lostvincent 2021-07-02 10:09:15 +08:00  2
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 |
|
2
lostvincent 2021-07-02 10:11:25 +08:00 1
上一楼写错 case 了，当成找不大于不小于到了，抱歉
|
|
3
lostvincent 2021-07-02 10:21:34 +08:00 1
他这里是 while lo < hi, hi = mid - 1 之后，如果 hi == lo，就不会进 while，这时候如果 nums[lo] == target，那么结果就会变成 -1
更正 case：nums = [4,5,6,7,0,1,2] target = 0 |
 |
4
xiaoming1992 OP @lostvincent 非常感谢！这个题目昨晚卡了我很久，一直想不通 high - 1 和 low + 1 有什么区别，原来区别出在 floor 这儿，感谢感谢！
|
Select Language