Leetcode 702) Search in a Sorted Array of Unkown Size
in Algorithms
My solution
- 오 감이 잡히는 듯? 이것도 한번에 맞았다!
- array의 크기를 먼저 구하고 했긴했는데, 생각해보니까 굳이 어레이 크기 안구해도 되네?
/**
* // 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) {
//I can search array length from doing BS for reader.
//and then do normal binary search to find target.
int left= 0;
int right= 10000;
//I need to access to the right element of mid!
// meaning, I want at least 2 elements when I go into while loop.
int secEndInd=0;
while(left<right){
int mid = left + (right-left)/2;
//if secret[mid] is equal to Integer max value,
if(reader.get(mid)!=Integer.MAX_VALUE && reader.get(mid+1)==Integer.MAX_VALUE){
//this is the length ind..
secEndInd=mid;
break;
}else if(reader.get(mid) ==Integer.MAX_VALUE){
//then move right to mid
//when there is only 2 elements in array, mid falls down to left. so if i give right= mid-1, it will cause index out of bound problem.
right= mid;
}else if(reader.get(mid)!=Integer.MAX_VALUE){
//reader.get(mid+1)!=INTEGER.MAX_VALUE;
left= mid+1;
}
}
//when it comes out, there is one pointer to check.
//and that is going to be only if when the length of secret is max.
//secret cannot be null
if(secEndInd==0){
secEndInd=999;
}
//now do the normal bs to search the target.
left= 0;
right= secEndInd;
//I don't need to access to neigbor elements, examine all the elements!
while(left<=right){
int mid = left + (right-left)/2;
if(reader.get(mid)==target){
return mid;
}else if(reader.get(mid)<target){
left= mid+1;
}else{
//reader.get(mid) > target
right=mid-1;
}
}
return -1;
}
}
- 그런데 성능 차이는 별로 없다.
/**
* // 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) {
//I can search array length from doing BS for reader.
//and then do normal binary search to find target.
int left= 0;
int right= 10000;
//I don't need to access to neigbor elements, examine all the elements!
while(left<=right){
int mid = left + (right-left)/2;
if(reader.get(mid)==target){
return mid;
}else if(reader.get(mid)<target){
left= mid+1;
}else{
//reader.get(mid) > target
right=mid-1;
}
}
return -1;
}
}
Other Answer
/**
* // This is ArrayReader's API interface.
* // You should not implement it, or speculate about its implementation
* interface ArrayReader {
* public int get(int index) {}
* }
*/
import java.lang.Math;
class Solution {
public int search(ArrayReader reader, int target) {
//Approach 2:
int high=1;
while(reader.get(high)!=Math.pow(2,31)-1){
high*=2;
}
return bSearch(reader,0,high,target);
}
int bSearch(ArrayReader reader, int low, int high, int element) {
if (high >= low) {
int mid = low+(high-low)/2;
if (reader.get(mid)== element) return mid ;
if (reader.get(mid) > element) return bSearch(reader, low, mid - 1, element);
else if (reader.get(mid) < element) return bSearch(reader, mid + 1, high, element);
}
return -1;
}
}
