Skip to content

Instantly share code, notes, and snippets.

@Jeffwan
Last active August 29, 2015 13:56
Show Gist options
  • Save Jeffwan/8837424 to your computer and use it in GitHub Desktop.
Save Jeffwan/8837424 to your computer and use it in GitHub Desktop.
Search for a Range @leetcode
package leetcode.binarySearch;
/**
* Solution: BinarySearch, two time. 2 O(logn) --> O(logn)
* Search left bound first and then search right bound second time.
* left: end = mid. right: start = mid. keeps we don't abandon result.
*
* Take care: sequence --> target == A[start] or A[end]. left bound should check start first, right check end.
*
* @author jeffwan
* @date Mar 9, 2014
*/
public class SearchRange {
public int[] searchRange(int[] A, int target) {
int[] bound = new int[2];
int start, end, mid;
if (A == null || A.length == 0) {
bound[0] = bound[1] = -1;
return bound;
}
// search the left bound, end = mid;
start = 0;
end = A.length - 1;
while(start + 1 < end) {
mid = start + (end - start) / 2;
if (target == A[mid]) {
end = mid;
} else if (target < A[mid]) {
end = mid;
} else {
start = mid;
}
}
if (target == A[start]) {
bound[0] = start;
} else if ( target == A[end]) {
bound[0] = end;
} else {
bound[0] = bound[1] = -1;
return bound;
}
// search the right bound, start = mid;
start = 0;
end = A.length - 1;
while (start + 1 < end) {
mid = start + (end - start) /2 ;
if (target == A[mid]) {
start = mid;
} else if (target < A[mid]) {
end = mid;
} else {
start = mid;
}
}
// sequence is very important here! test case [2,2] 2 -- if start go first, result will be [0,0]
if (target == A[end]) {
bound[1] = end;
} else if ( target == A[start]) {
bound[1] = start;
}
return bound;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment