Search in a Big Sorted Array(Ladder)

Description

Given a big sorted array with positive integers sorted by ascending 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.

Notice
If you accessed an inaccessible index (outside of the array), ArrayReader.get will return 2,147,483,647.

Example:
Given [1, 3, 6, 9, 21, ...], and target = 3, return 1.
Given [1, 3, 6, 9, 21, ...], and target = 4, return -1.

Challenge:
O(log k), k is the first index of the given target number.

Link

Lintcode-ladder

Method

1. Binary Search O(logk)
2. x

Example

1. 1

   /**
   * Definition of ArrayReader:
   * 
   * class ArrayReader {
   * public:
   *     int get(int index) {
   *          // return the number on given index, 
   *          // return -1 if index is less than zero.
   *     }
   * };
   */
   class Solution {
   public:
    /**
     * @param reader: An instance of ArrayReader.
     * @param target: An integer
     * @return: An integer which is the first index of target.
     */
    int searchBigSortedArray(ArrayReader *reader, int target) {
        // write your code here
        if (!reader) {
            return -1;
        }
        // find range of search
        int range = 1;
        // find the max index including target
        while (reader->get(range-1) < target && reader->get(range-1) != -1) {
            range *= 2;
        }
        // the range can be limited in here
        int start = range/2 -1;
        int end = range -1;
        while (start+1 < end) {
            int mid = start + (end-start)/2;
            int mid_val = reader->get(mid);
            if (target <= mid_val) {
                end = mid;
            } else {
                start = mid;
            }
        }
        if (target == reader->get(start)) {
            return start;
        }
        if (target == reader->get(end)) {
            return end;
        }
        return -1;
    }
   };
   

Similar problems

x

Tags

x