什么是二分法查找
二分法检索(binary search)称折半检索
二分法查找的基本思想
前提：
-
数组中的元素从小到大有序的存放在数组(array)中
步骤：
-
将给定值key与数组中间位置元素的关键码(key)比较
-
如果相等，检索成功
-
key小，在数组前半段继续二分查找
-
key大，在数组后半段进行二分查找，直到索引成功
对于有序数组而言，二分查找的效率是比较高的
实例：
package com.array;
import java.util.Arrays;
/**
* 测试二分法查找，折半检索,通过值找索引
* @author Lucifer
*/
public class TestBinarySearch {
public static void main(String[] args) {
/*测试源数组*/
int[] arr = {30,20,50,10,80,9,7,12,100,40,8};
/*
1.排序---不用冒泡排序，用工具类方法
2.定义检索的范围---定义两个变量，起始位置、结束位置
*/
Arrays.sort(arr);
//要查找的值
// int value = 10;
System.out.println(Arrays.toString(arr));
System.out.println(myBinarySearch(arr,-1));
}
/*封装返回值*/
/*
传进来的值进行查找
在arr数组中查找
这样就定义了形参
*/
public static int myBinarySearch(int[] arr, int value){
/*测试二分查找*/
//起始位置
int low = 0;
//结束位置
int high = arr.length - 1; //最大索引值
//循环条件
while (low <= high){
//定义中间索引值
int mid = (low + high)/2;
//相等说明找到了，直接返回值
if (value == arr[mid]){
return mid;
}
//如果值比中间索引值要大，说明要从中间索引向后找，所以起始位置索引要变成中间索引值+1
if (value > arr[mid]){
low = mid + 1;
}
// //如果值比中间索引值小，说明要从中间索引向前找，所以起始位置索引要变成中间索引值-1
// if (value < arr[mid]){
// low = mid - 1;
// }
//如果值比中间索引值小，说明要从中间索引向前找，所以起始位置索引要变成中间索引值-1
if (value < arr[mid]){
high = mid - 1;
}
/*
注意这里是high最大值发生变化不是最小值发生变化
如果是写最小值low变化在进行到第三次while循环的时候
从low到high的元素数量变成偶数，通过(low + high)/2取得的mid一直为8
low就会始终为7
所以程序会出现死循环，运行不下去
*/
}
//没有找到返回-1
return -1;
}
}