变形一：查找第一个等于给定值的元素
/**
* 返回的是数组下标
* @param a
* @param n 数组大小
* @param value
* @return
*/
public static int binarySearch(int[] a, int n , int value){
int low = 0;
int high = n-1;
while (low <= high){
int mid = low + (high-low)/2;
if (a[mid] > value){
low = mid+1;
}
else if (a[mid] < value){
high = mid -1;
}
else {
//如果a[mid] == value 的话mid == 0 说明是数组的第一个元素，肯定是第一出现的元素，
// 或者mid的前一个元素不是value那么mid就是第一个出现元素的下标
if ((mid == 0) || a[mid -1 ] != value)return mid;
else {
//否则第一个出现的元素就是在low 到 mid -1之间
high = mid -1;
}
}
}
return -1;
}
变体二:查找最后一个值等于给定值得元素
/**
* 变体二查找最后一个值等于给定值得元素
* @param a
* @param n
* @param value
* @return
*/
public int bsearch2(int[] a, int n, int value) {
int low = 0;
int high = n - 1;
while (low <= high) {
int mid = low + ((high - low) >> 1);
if (a[mid] > value) {
high = mid - 1;
} else if (a[mid] < value) {
low = mid + 1;
} else {
//如果是数组最后一个元素，那么肯定是最后一个
// 或者mid的下一个元素的值不等于给定值，mid就是最后一个等于给定值的元素下标
if ((mid == n - 1) || (a[mid + 1] != value)) return mid;
//否则就在mid+1 到 high之间
else low = mid + 1;
}
}
return -1;
}
变体三：查找第一个大于等于给定值的元素
/**
* 变体三：查找第一个大于等于给定值的元素
* @param a
* @param n
* @param value
* @return
*/
public int bsearch3(int[] a, int n, int value) {
int low = 0;
int high = n - 1;
while (low <= high) {
int mid = low + ((high - low) >> 1);
if (a[mid] >= value) {
//当a[mid]大于等于value的时候，mid如果等于0那么a[mid]就是第一个大于或等于给定值的元素，
//或者mid的前一个元素小于给定值，那么mid就是第一个大于等于给定值的元素的下标
if ((mid == 0) || (a[mid - 1] < value)) return mid;
//否则就在low 到 mid-1 之间
else high = mid - 1;
} else {
low = mid + 1;
}
}
return -1;
}
变体四：查找最后一个小于等于给定值的元素
/**
* 变体四：查找最后一个小于等于给定值的元素
* @param a
* @param n
* @param value
* @return
*/
public int bsearch4(int[] a, int n, int value) {
int low = 0;
int high = n - 1;
while (low <= high) {
int mid = low + ((high - low) >> 1);
if (a[mid] > value) {
high = mid - 1;
} else {
if ((mid == n - 1) || (a[mid + 1] > value)) return mid;
else low = mid + 1;
}
}
return -1;
}
