本文共 2295 字，大约阅读时间需要 7 分钟。

Given a big sorted array with non-negative integers sorted by non-decreasing order. The array is so big so that you can not get the length of the whole array directly, and you can only access the kth number by ArrayReader.get(k) (or ArrayReader->get(k) for C++).

Find the first index of a target number. Your algorithm should be in O(log k), where k is the first index of the target number.

Return -1, if the number doesn’t exist in the array.

Example 1:

Input: [1, 3, 6, 9, 21, …], target = 3

Output: 1

Example 2:

Input: [1, 3, 6, 9, 21, …], target = 4

Output: -1

我的想法

没有尾巴的二分法。。。。。不知道该怎么做

解答

**jiuzhang solution 1: 倍乘法 **

/** * Definition of ArrayReader: *  * public class ArrayReader { * public int get(int index) { *          // return the number on given index,  *          // return 2147483647 if the index is invalid. *     } * }; */public class Solution {
       public int searchBigSortedArray(ArrayReader reader, int target) {
           int firstElem = reader.get(0);        if(firstElem == target) {
               return 0;        }        if(firstElem > target) {
               return -1;        }                //multiplication        int idx = 0;        int jump = 1;        while(jump != 0) {
           //be careful! it's '>='. don't forget '='            while(jump != 0 && reader.get(idx + jump) >= target) {
                   jump /= 2;            }            idx += jump;            jump *= 2;        }        if(reader.get(idx + 1) == target) {
               return idx + 1;        }        return -1;    }}

jiuzhang solution 2: 二分法

public class Solution {
       public int searchBigSortedArray(ArrayReader reader, int target) {
           //to find the boundary        int start = 0, end = 1;        while(reader.get(end) <= target) {
               end *= 2;        }                //binary search        while(start + 1 < end) {
               int mid = start + (end - start) / 2;            if(reader.get(mid) < target) {
                   start = mid + 1;            }            if(reader.get(mid) >= target) {
                   end = mid;            }        }        if(reader.get(start) == target) {
               return start;        }        if(reader.get(end) == target) {
               return end;        }        return -1;    }}

转载地址：http://qkqvb.baihongyu.com/