原式：最简单的二分查找
public static int search(int[] arr, int value) {
int left=0;
int right = arr.length - 1;
while (left <= right) {
int mid = left + ((right - left) >> 1);
if (arr[mid] == value) {
return mid;
} else if (arr[mid] < value) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
注意1：求mid时，使用 int mid = left + ((right - left) >> 1); 代替 int mid = (right + left) / 2; 避免整数越界。
注意2：当数组中存在重复元素时，二分查找只能找出第一个满足相等条件的目标值。
举个例子：二分查找a[10]中的8，会找到a[7]，即第3个8。
4个变式问题
变式1：二分查找目标值的左侧边界
public static int searchFirst(int[] arr, int value) {
int low = 0;
int high = arr.length - 1;
while (low <= high) {
int mid = low + ((high - low) >> 1);
if (arr[mid] > value) {
high = mid - 1;
} else if (arr[mid] < value) {
low = mid + 1;
} else if (arr[mid] == value) {
// 若mid是数组第一个数时，表示找到了左边界
// 若mid前一个数不是目标值，表示找到了左边界
if (mid == 0 || arr[mid - 1] != value) {
return mid;
}
// 若不满足条件，则左边界在[low,mid-1]区间
else {
high = mid - 1;
}
}
}
return -1;
}
和原式二分查找的区别在于arr[mid] == value的情况：
在中间值等于目标值时，无法判断这个中间值是目标值左边界，所以要做以下判断：
-
mid==0→若mid是数组第一个数时，表示找到了左边界 -
arr[mid - 1] != value→若mid前一个数不是目标值，表示找到了左边界
若不满足以上两个条件，则左边界在[low,mid-1]区间
变式2：二分查找目标值的右侧边界
public static int searchLast(int[] arr, int value) {
int low = 0;
int high = arr.length - 1;
while (low <= high) {
int mid = low + ((high - low) >> 1);
if (arr[mid] > value) {
high = mid - 1;
} else if (arr[mid] < value) {
low = mid + 1;
} else if (arr[mid] == value) {
// 若mid是数组最后一个数时，表示找到了右边界
// 若mid后一个数不是目标值，表示找到了右边界
if (mid == arr.length - 1 || arr[mid + 1] != value) {
return mid;
}
// 若不满足条件，则左边界在[mid+1,high]区间
else {
low = mid + 1;
}
}
}
return -1;
}
与变式1同理，更改一下arr[mid] == value的判断即可。
变式3：查找第一个大于等于目标值的元素
public static int searchFirstGreaterOrEqual(int[] arr, int value) {
int low = 0;
int high = arr.length - 1;
while (low <= high) {
int mid = low + ((high - low) >> 1);
if (arr[mid] < value) {
low = mid + 1;
} else if (arr[mid] >= value) {
// 若mid是数组第一个数时，表示找到了第一个大于等于目标值的元素
// 若mid前一个数小于目标值，表示找到了第一个大于等于目标值的元素
if (mid == 0 || arr[mid - 1] < value) {
return mid;
}
// 若不满足条件，则第一个大于等于目标值的元素在[low,mid-1]区间
else {
high = mid - 1;
}
}
}
return -1;
}
在arr[mid] >= value的情况下，无法判断这个中间值是第一个大于等于目标值的元素，所以要做以下判断：
-
mid==0→若mid是数组第一个数时，表示找到了第一个大于等于目标值的元素 -
arr[mid - 1] < value→若mid前一个数小于目标值，表示找到了第一个大于等于目标值的元素
若不满足以上两个条件，则第一个大于等于目标值的元素在[low,mid-1]区间
变式4：查找最后一个小于等于目标值的元素
public static int searchLastLessOrEqual(int[] arr, int value) {
int low = 0;
int high = arr.length - 1;
while (low <= high) {
int mid = low + ((high - low) >> 1);
if (arr[mid] > value) {
high = mid - 1;
} else if (arr[mid] <= value) {
// 若mid是数组最后一个数时，表示找到了最后一个小于等于目标值的元素
// 若mid后一个数大于目标值，表示找到了最后一个小于等于目标值的元素
if (mid == arr.length - 1 || arr[mid + 1] > value) {
return mid;
}
// 若不满足条件，则最后一个小于等于目标值的元素在[mid+1,high]区间
else {
low = mid + 1;
}
}
}
return -1;
}
与变式3同理，不做赘述。
