447. Search in a big sorted array

Leave a comment

September 29, 2016 by oneOokay

public int searchBigSortedArray(ArrayReader reader, int target) {
if (reader.get(0) > target) {
return -1;
}
if (reader.get(0) == target) {
return 0;
}
int index = 1;
while (reader.get(index) < target) {
index = index * 2;
} //以下为优化的
int index = 1;
while (reader.get(index – 1) < target) { //index不能为0,0 * 2 永远为0
index = index * 2;
}
int end = index;
int start = index / 2 – 1;
while (start + 1 < end) {
int mid = start + (end – start) / 2;
if (reader.get(mid) >= target) {
end = mid;
}else {
start = mid;
}
}

if (reader.get(start) == target) {
return start;
}
if (reader.get(end) == target) {
return end;
}

return -1;
}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: