leetcode702--search in a sroted array of unknown size

leetcode702--search in a sroted array of unknown size

题目意思

意思是给定一个排好序的数组,里面的值都是int类型的,但是并不知道这个数组有多长,然后任意给一个整数,要问的是这个整数在不在这个数组里面,是的话,就返回其index,如果没在的话,就返回-1.

还有一个要求是,我们不能用’.size()’之类的来求得其长度,要获得数组中某个值的元素的话,可以利用出题者已经写好的ArrayReader类的get方法来获得值,如果越界的话,就会返回整数的最大值–2147483647.

方法

初次看这个题目,想到的就是binary search,因为给的数组是排好数序的(从小到大),但是一个问题是不知道数组的长度,就不知道尾的位置。但是实际上题目里面已经给了提示。可以假设数组就是INT_MAX那么长,根据题目中说的,多的部分其值都是2147483647.这样就相当于知道了长度,然后就可以利用二分查找了。 c++代码如下。

class ArrayReader;

class Solution{
public:
        int search(const ArrayReader& reader, int target){
            int left=0, right=INT_MAX;
            while(left<right){
                int mid = left + (right-left)/2, x=reader.get(mid);
                if(x==target) return mid;
                else if(x<target) left=mid+1;
                else right=mid;
            }
            return -1;
        }
}

需要注意的是c++中整数的最大值和python中的整数的最大值是不一样的,在python里面可以用下面的办法查整数的最大值

>>> import sys
>>> sys.maxint
9223372036854775807

如果是python3的话,就用sys.maxsize.

下面是用python写的几个方案 先找边界的办法。

class Solution:
    def search(self, reader, target):
        hi =1
        while reader.get(hi)<target:
            hi *= 2
        
        # here target must be in (hi/2, hi)
        lo = int(hi/2)

        while lo<=hi:
            mid = lo + int((hi-lo)/2)
            v = reader.get(mid)
            if v==target: 
                return mid
            elif v>target:
                hi = mid-1
            else:
                lo = mid+1
        return -1

当然也可以从头找到底

i=0
while True:
    v = reader.get(i)
    if v==2147483647:  # 因为数组里面的值不会超过100000
        return -1
    if v==target:
        return i
    i += 1
return -1

打赏,谢谢~~

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,多谢支持~

打开微信扫一扫,即可进行扫码打赏哦