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>
