/**
* 二分法查找
*
使用二分法查找的前提数组已经排过序
*/
public class Demo4 {
public static void main(String[] args) {
int[] arr = { 3, 1, 8, 2, 9, 100, 33, 22, 11, 18, 14, 17, 15, 3 };
// 使用Arrays.sort()排序
Arrays.sort(arr);
System.out.println(Arrays.toString(arr));
// 返回结果
//int index = brinarySearch(arr, 99);
int index = brinarySearch_2(arr, 11);
System.out.println(“index=” + index);
}
/*
* 二分法查找一返回下标如果是-1就说明没有
*/
public static int brinarySearch(int[] arr, int key) {// 数组和要查找的数
int min = 0; // 最小的下标
int max = arr.length – 1;// 最大的下标
int mid = (min + max) / 2;// 中间的下标
while (arr[mid] != key) {
if (key > arr[mid]) { //比中间数还在
min = mid + 1; //最小的下标=中间下标加一
} else if (key < arr[mid]) {//比中间数还小
max = mid – 1; //最大的下标=中间下标-1
}
if(max<min){
return -1;
}
mid=(min+max)/2; //再次计算中间下标
}
return mid;
}
/*
* 二分法查找一返回下标如果是-1就说明没有
*/
public static int brinarySearch_2(int[] arr, int key) {// 数组和要查找的数
int min = 0; // 最小的下标
int max = arr.length – 1;// 最大的下标
int mid = (min + max) / 2;// 中间的下标
while(min<=max){
if(key>arr[mid]){
min=mid+1;
}else if(key<arr[mid]){
max=mid-1;
}else{
return mid;
}
mid=(min+max)/2;
}
//没找到
return -1;
}
}
转载请注明来源网站:blog.ytso.com谢谢！
原创文章，作者：ItWorker，如若转载，请注明出处：https://blog.ytso.com/tech/pnotes/14927.html