LeetCode [702] Search in a Sorted Array of Unknown Size

 702. Search in a Sorted Array of Unknown Size

Medium

Given an integer array sorted in ascending order, write a function to search target in nums.  If target exists, then return its index, otherwise return -1. However, the array size is unknown to you. You may only access the array using an ArrayReader interface, where ArrayReader.get(k) returns the element of the array at index k (0-indexed).

You may assume all integers in the array are less than 10000, and if you access the array out of bounds, ArrayReader.get will return 2147483647.

 

Example 1:

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

Example 2:

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 [-9999, 9999].
• The length of the array will be in the range [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 30 31 32

/** * // 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 { int N = 10000; int M = 2147483647; public int search(ArrayReader reader, int target) { int l = 0, r = N; while(l<=r){ int m = (l+r)/2; int res = reader.get(m); if(res==M){ r = m-1; }else{ if(res==target){ return m; } if(res<target){ l = m+1; }else{ r = m-1; } } } return -1; } }

YMSF

第四轮是面coding，有个indefinitely long list of words A，你不能直接access，只能call A.get(i)来得到第i个word，word是sorted，要查找一个word，返回在list里的index，followup是要你写一个A这样的object用来测试你的code，最后的followup是，我用了2^n的增速在寻找index的上边界，再binary search上下边界之间的word，小哥问有没有更快的算法，其实是问有没有比2^n增速更快的a^n的a能使整体time complexity更低

我的做法是写一个class，一个variable是list of word，一个function get，如果get输入大于等于list的长度，返回一个无穷大，跟任何str比都要大，如果输入在范围内，返回word