Search in a Big Sorted Array
Written on October 27, 2015
Tweet
Given a big sorted array, find the first index of a target number. Your algorithm should be in O(log k), where k is the first index of the target number. Return -1, if the number doesn't exist in the array.
public class Solution {
/**
* @param A: An integer array
* @param target: An integer
* @return : An integer which is the index of the target number
*/
public int searchBigSortedArray(int[] A, int target) {
// write your code here
if (A == null || A.length == 0) return -1;
int lo = 0, hi = 0;
while (hi < A.length && A[hi] < target) {
hi = 2 * hi + 1;
}
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (A[mid] == target) {
while (mid - 1 >= 0 && A[mid - 1] == A[mid]) {
mid--;
}
return mid;
} else if (A[mid] > target) {
hi = mid - 1;
} else {
lo = mid + 1;
}
}
return -1;
}
}