折半查找和二分查找区别(折半查找二分法)
导语：常见操作三：折半查找（二分查找）
class ArrayDemo{
public static void main(String[] args) {
int[] arr= {4,1,5,7,8,4,2};
int index = getIndex(arr,2);
System.out.println("index = " + index);
}
public static int getIndex(int[] arr, int key){
for(int x = 0; x < arr.length; x++){
if(arr[x] == key)
return x;
}
return -1;
}
}
运行结果： P.S.如果一个数组是无序的，那么可以通过简单遍历查找的方式查找到某个元素所在的角标。但是如果一个数组是有序的，那么就可以通过一种更高效的方式达到相同的目的，也就是二分查找。
思路：1、设置三个变量记录角标：min、max、mid。min初始值为0，max为数组最大角标，mid为（max+min）/2。
2、查看mid角标的元素是否与待查找的值相等，如果相等，则直接返回角标值，程序终止执行。
3、如果待查找的值小于角标为mid的元素值，那么说明待查找的元素的位置可能在min与mid角标之间。设置max = mid - 1，mid = (max + min)/2，重复第1、2步的操作。
4、如果待查找的值大于角标为mid的元素值，那么说明待查找的元素的位置可能在mid与max角标之间。设置min = mid + 1，mid = (max + min)/2，重复第1、2步的操作。
5、如果数组中不存在待查找的元素，那么按照如上流程，最终min角标值会大于max角标值，此时返回-1。
代码1：class ArrayDemo{
public static void main(String[] args) {
int[] arr= {13,15,19,28,33,45,78,106};
int index = binarySearch(arr,78);
System.out.println("index = " + index);
}
public static int binarySearch(int[] arr, int key){
int max,min,mid;
min = 0;
max =arr. length - 1;
mid = (max + min)/2;
while(arr[mid] !=key){
if(key > arr[mid])
min = mid + 1;
else if (key < arr[mid])
max = mid - 1;
if(max < min)
return -1;
mid = (max + min)/2;
}
return mid;
}
}
运行结果： 代码2：class ArrayDemo{
public static void main(String[] args) {
int[] arr= {13,15,19,28,33,45,78,106};
int index = binarySearch(arr,78);
System.out.println("index = " + index);
}
public static int binarySearch(int[] arr, int key){
int max,min,mid;
min = 0;
max = arr. length - 1;
while(min <= max){
mid = (max + min) >> 1;
if(key > arr[mid])
min = mid + 1;
else if (key < arr[mid])
max = mid - 1;
else
return mid;
}
return -1;
}
}
运行结果： P.S.给定一个有序的数组，如果往该数组中存储一个元素，并保证这个数组还是有序的，那么这个元素的存储的角标如何获取？
可以先通过二分查找，返回min的值，然后将待插入元素存在角标为min的数组位置，数组中角标为min以及比min大的角标所在的数组元素全部往后顺延一个位置。
代码：class ArrayDemo{
public static void main(String[] args) {
int[] arr= {13,15,19,28,33,45,78,106};
int index = binarySearch(arr,44);
System.out.println("index = " + index);
}
public static int binarySearch(int[] arr, int key){
int max,min,mid;
min = 0;
max = arr. length - 1;
while(min <= max){
mid = (max + min) >> 1;
if(key > arr[mid])
min = mid + 1;
else if (key < arr[mid])
max = mid - 1;
else
return mid;
}
return min;
}
}
运行结果：说明：由上面的结果可以看到，如果要向数组{13,15,19,28,33,45,78,106}中插入值为44的元素，那么应该插入的位置角标是5，角标为5以及其后的元素都应该往后顺延一个位置。
P.S.在实际开发中，二分查找也不需要我们自己去写，JDK中已经提供了相关的API供调用。
示例：import java.util.Arrays;
class ArrayDemo{
public static void main(String[] args) {
int[] arr= {13,15,19,28,33,45,78,106};
//如果存在返回的具体的角标位置，不存在返回的是-插入点-1
int index = Arrays.binarySearch(arr,44);
System.out.println("index = " + index );
}
}
运行结果：说明：返回的是-6而不是5的原因可以通过API文档查找到.
本文内容由小冰整理编辑！