GuilinDev

Lc0702

05 August 2008

702 Search in a Sorted Array of Unknown Size

原题

Given an integer array sorted in ascending order, write a function to search 

1

target
in 
1

nums
. If 
1

target
exists, then return its index, otherwise return 
1

-1
. However, the array size is unknown to you. You may only access the array using an 
1

ArrayReader
interface, where 
1

ArrayReader.get(k)
returns the element of the array at index 
1

k
(0-indexed).

You may assume all integers in the array are less than 

1

10000
, and if you access the array out of bounds, 
1

ArrayReader.get
will return 
1

2147483647
.

Example 1:

1
2
3

Input: array = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4

Example 2:

1
2
3

Input: array = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1

Constraints:

  • You may assume that all elements in the array are unique.
  • The value of each element in the array will be in the range 
    1

    [-9999, 9999]
    .
  • The length of the array will be in the range 
    1

    [1, 10^4]
    .

分析

倍增找到右边界，然后二分。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

/**
 * // This is ArrayReader's API interface.
 * // You should not implement it, or speculate about its implementation
 * interface ArrayReader {
 *     public int get(int index) {}
 * }
 */

class Solution {
    public int search(ArrayReader reader, int target) {
        long left = 0, right = 1;
        while (reader.get((int)right) < target) {
            right *= 2;
        }
        while (left + 1 < right) {
            long mid = left + (right - left) / 2;
            if (reader.get((int)mid) == target) {
                return (int)mid;
            } else if (reader.get((int)mid) < target) {
                left = mid;
            } else {
                right = mid;
            }
        }
        if (reader.get((int)left) == target) return (int)left;
        
        return reader.get((int)right) == target ? (int)right : -1;
    }
}
This site is open source. Improve this page.