二分查找,就是在有序的线性表中查找特定元素,每次查找时直接比较中间元素,如果中间元素比目标值大,就往左侧区间找;如果中间元素比目标值小,就往右侧区间找;如果相等,说明找到了!
public static int search(int[] arr, int target){
int lo = 0, hi = arr.length - 1;
int mid = 0;
while (lo <= hi) {
mid = lo + ((hi - lo) >> 1);
if (arr[mid] > target) {
hi = mid - 1;
} else if (arr[mid] < target) {
lo = mid + 1;
}else{
return mid;
}
}
return -1;
}
但是呢,它的查找非常容易错,就是在一些变形问题上,比如查找第一个等值的元素、最后一个等值元素、第一个大于等于值的元素、最后一个小于等于值的元素。下面贴一下代码,以后可以复看。
我觉得现在学到一个技巧:不追求完美的写法,把逻辑写清楚就行。
public class Search {
public static void main(String[] args) {
int[] arr = {
1, 3, 4, 5, 6, 8, 8, 8, 8, 9, 12
};
System.out.println(search(arr, 3));
System.out.println(searchLeft(arr, 8));
System.out.println(searchRight(arr, 8));
System.out.println(searchFirstGreaterValue(arr, 7));
System.out.println(searchLastLesserValue(arr, 7));
}
public static int search(int[] arr, int target){
int lo = 0, hi = arr.length - 1;
int mid = 0;
while (lo <= hi) {
mid = lo + ((hi - lo) >> 1);
if (arr[mid] > target) {
hi = mid - 1;
} else if (arr[mid] < target) {
lo = mid + 1;
}else{
return mid;
}
}
return -1;
}
public static int searchLeftShort(int[] arr, int target) {
int lo = 0, hi = arr.length - 1;
int mid = 0;
while (lo <= hi) {
mid = lo + ((hi - lo) >> 1);
if (arr[mid] >= target) {
hi = mid - 1;
} else if (arr[mid] < target) {
lo = mid + 1;
}
}
// 跳出循环的时候再测
if (lo < arr.length && arr[lo] == target) {
return lo;
}
return -1;
}
public static int searchLeft(int[] arr, int target) {
int lo = 0, hi = arr.length - 1;
int mid = 0;
while (lo <= hi) {
mid = lo + ((hi - lo) >> 1);
if (arr[mid] > target) {
hi = mid - 1;
} else if (arr[mid] < target) {
lo = mid + 1;
} else {
// 看看前一个是否是目标值,也是,就说明还没有找到最左一个
if (mid == 0 || arr[mid - 1] != target) {
return mid;
} else {
hi = mid - 1;
}
}
}
return -1;
}
public static int searchRight(int[] arr, int target) {
int lo = 0, hi = arr.length - 1;
int mid = 0;
while (lo <= hi) {
mid = lo + ((hi - lo) >> 1);
if (arr[mid] > target) {
hi = mid - 1;
} else if (arr[mid] < target) {
lo = mid + 1;
} else {
if (mid == arr.length - 1 || arr[mid + 1] != target) {
return mid;
} else {
lo = mid + 1;
}
}
}
return -1;
}
public static int searchFirstGreaterValue(int[] arr, int target) {
int lo = 0, hi = arr.length - 1;
int mid = 0;
while (lo <= hi) {
mid = lo + ((hi - lo) >> 1);
if (arr[mid] >= target){
if (mid == 0 || arr[mid - 1] < target){
return mid;
}
hi = mid - 1;
}else{
lo = mid + 1;
}
}
return -1;
}
public static int searchLastLesserValue(int[] arr, int target){
int lo = 0, hi = arr.length - 1;
int mid = 0;
while (lo <= hi) {
mid = lo + ((hi - lo) >> 1);
if (arr[mid] > target){
hi = mid - 1;
}else{
if (mid == arr.length - 1 || arr[mid + 1] > target){
return mid;
}
lo = mid + 1;
}
}
return -1;
}
}