guibin
BAN USER/**
* Find the first occurance of a number in a sorted array.
*
* @param arr The array to be searched.
* @param target
* @return The index of the first occurance, return -1 if not found.
*/
public int searchFirstOccurance(int[] arr, int target) {
int lo = 0;
int hi = arr.length;
while(lo < hi) {
int mid = lo + (hi - lo)/2;
if(arr[mid] < target) {
lo = mid + 1;
} else if(arr[mid] > target) {
hi = mid - 1;
} else {//arr[mid] == target
hi = mid;
}
}
if(arr[lo] == target)
return lo;
else return -1;
}
You didn't consider the case that the step has duplicate start point.
- guibin August 13, 2014