Search in a Big Sorted Array

Search in a Big Sorted Array.png

===================== 解題思路 =====================

跟 first position of target 基本一樣的題型 只是多了一道手續 要先找到 end 的位置, 可以從 index = 1 開始找 每次乘以二 一旦找到比 target 大的數就停下 當做 end 的 index, 接下來就是一模一樣了

===================== C++ code ====================

<pre><code>
/**

• 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
    int left = 0, right = 1;
    while(reader->get(right) < target)
    {
        right *= 2; 
    }
    
    while(left + 1 < right)
    {
        int mid = left + (right - left) / 2;
        if(reader->get(mid) >= target) right = mid;
        else left = mid;
    }
    if(reader->get(left) == target) return left;
    if(reader->get(right) == target) return right;
    return -1;
}

};
<code><pre>