lc702, 二分法while(left+1<right)就不行？

大佬们好，
这道题是search in a sorted unknown size array, 前面都写的好好的，就是后面二分法的时候program crash掉了
而且这个也不好写进IDE debug,
邪了门了，只要leetcode 题里带有interface的我全都做不对，
这里的的话，我按照往常的写法判断二分法的条件while(left+1<right)就不行，而while(left<=right)的写法就可以，
请问为什么？实在想不出，求大佬指出【lc中的ArrayReader.get(k)是这里的dict,get(k)】

1. public class Solution {
   
2.   public int search(Dictionary dict, int target) {
   
3.     int left=0, right=1;
   
4.     while(dict.get(right)!=null && dict.get(right)<target){
   
5.       left=right;
   
6.       right=2*right;
   
7.     }
   
8.     return binarySearch(dict,target, left,right);
   
9.   }
   
10. 
    
11.   private int binarySearch(Dictionary dict, int target, int left, int right){
    
12.     //Here do classical binary search,works
    
13.     // while(left<=right){
    
14.     //   int mid=left+(right-left)/2;
    
15.     //   if(dict.get(mid)==null || dict.get(mid)>target){
    
16.     //     right=mid-1;
    
17.     //   }else if(dict.get(mid)<target){
    
18.     //     left=mid+1;
    
19.     //   }else{
    
20.     //     return mid;
    
21.     //   }
    
22.     // }
    
23.     // 并不知道为啥用变种做法就不可以
    
24.     while(left+1<right){
    
25.       int mid=left+(right-left)/2;
    
26.       if(dict.get(mid)==null || dict.get(mid)>target){
    
27.         right=mid;
    
28.       }else if(dict.get(mid)<target){
    
29.         left=mid;
    
30.       }else{
    
31.         return mid;
    
32.       }
    
33.     }
    
34.     if(dict.get(left)==target) return left;
    
35.     if(dict.get(right)==target) return right;
    
36.     return -1;
    
37.   }
    
38. }

复制代码

先在此谢过

我最近也在纠结二分查找，现在已经差不多想明白了，很多细节确实很烦。楼主这两个模版应该问题不大，不过需要多注意一些corner case。

akdhfikbk 发表于 2019-10-29 11:15
我觉得应该是left跳出界了，XXXXXXXXXXXXXXXXX_____________Leftleft已经超出boundary，所以left==null了 ...

嗯，应该是这么个情况。我觉得你可以写 if(dict.get(left) != null && dict.get(left) == target) 试一下，这样如果第一个不成立就直接返回了。

akdhfikbk 发表于 2019-10-29 06:52
可是我的compiler就跑不通啊摔！
生气！
program crash了啊 啊啊啊啊啊！

你在lc上的代码发出来看看呗。我就是用的这个。不过是 ！= null换成了 大于10000， 题目描述就是小于这个数。等于null那个条件我去掉了，那么大的整数肯定大于。。

现在还是dictionary吗。。我感觉好像不是吧。。好像是大的整数，我用你的这个代码，把== null那里改成了 > 10000都跑得过啊。

不知道小帅 发表于 2019-10-29 04:30
现在还是dictionary吗。。我感觉好像不是吧。。好像是大的整数，我用你的这个代码，把== null那里改成了 >  ...

你用我的while(left+1<right) 这个写法吗》

akdhfikbk 发表于 2019-10-29 06:31
你用我的while(left+1

就是复制了你的代码，就过了。肯定是这个啊。。前面都被注释掉了啊。

不知道小帅 发表于 2019-10-29 06:33
就是复制了你的代码，就过了。肯定是这个啊。。前面都被注释掉了啊。

可是我的compiler就跑不通啊摔！
生气！
program crash了啊 啊啊啊啊啊！

不知道小帅 发表于 2019-10-29 06:56
你在lc上的代码发出来看看呗。我就是用的这个。不过是 ！= null换成了 大于10000， 题目描述就是小于这个 ...

贴在这里了 https://ibb.co/x2tr2Nn
谢谢你先哈

akdhfikbk 发表于 2019/10/29 08:32:34


贴在这里了 https://ibb.co/x2tr2Nn
谢谢你先哈

估计是因为left那里越界了吧？

不知道你怎么写的题目， function signature长得不一样，你的Dictionary不知道是什么， 我只能看见ArrayReader。