关于查找算法中的：二分法查找。
- 10(下标0) 11 12 13 14 15 16 17 18 19 20(下标10) arr数组。
通过二分法查找，找出18这个元素的下标：
- (0 + 10) / 2 –> 中间元素的下标： 5
拿着中间这个元素和目标要查找的元素进行对比：
- 中间元素是：arr[5] –> 15
- 15 < 18(被查找的元素)
- 被查找的元素18在目前中间元素15的右边。
- 所以开始元素的下标从0变成 5 + 1.
再重新计算一个中间元素的下标：
- 开始下标是：5 + 1
- 结束下标是：10
- (6 + 10) / 2 –> 8
8下标对应的元素arr[8]是18
找到的中间元素正好和被找的的元素18相等，表示找到了：下标为8
二分法查找的终止条件：一直折半，直到中间的那个元素恰好是被查找的元素。
二分法查找算法是基于排序的基础之上。（没有排序的数据是无法查找的。）
二分法查找效率要高于“一个挨着一个”的这种查找方式。
二分法查找原理：
10(0下标) 23 56 89 100 111 222 235 500 600(下标9) arr数组
目标：找出600的下标
(0 + 9) / 2 –> 4（中间元素的下标）
arr[4]这个元素就是中间元素：arr[4]是 100
100 < 600
说明被查找的元素在100的右边。
那么此时开始下标变成：4 + 1
(5 + 9) / 2 –> 7（中间元素的下标）
arr[7] 对应的是：235
235 < 600
说明被查找的元素在235的右边。
开始下标又进行了转变：7 + 1
(8 + 9) / 2 –> 8
arr[8] –> 500
500 < 600
开始元素的下标又发生了变化：8 + 1
(9 + 9) / 2 –> 9
arr[9]是600，正好和600相等，此时找到了。
示例代码：
public class ArrayUtil {
public static void main(String[] args) {
int arr[] = {100,200,230,235,600,1000,2000,9999};
int index = binarySearch(arr,9999);
System.out.println(index == -1 ? "该元素不存在" : "该元素的下标为：" + index);
}
/**
*从数组中查找目标元素的下标
* @param arr 被查找的数组（这个必须是已经排序的）
* @param dest 目标元素
* @return -1表示该元素不存在，其次它表示返回该元素的下标
*/
public static int binarySearch(int[] arr, int dest) {
//开始元素下标
int begin = 0;
//结束元素下标
int end = arr.length-1;
//开始元素的下标只要在结束元素下标的左边，就有机会继续循环
while(begin <= end) {
//中间元素下标
int mid = (begin + end) / 2;
if (arr[mid] == dest) {
return mid;
} else if (arr[mid] < dest) {
//目标在中间的右边
//开始元素下标需要发生变化（开始元素的下标需要重新赋值）
begin = mid + 1;//一直增
}else {
//arr[mid] < dest
//目标元素在中间的左边
//修改结束元素的下标
end = mid - 1;//一直减
}
}
return -1;
}
运行结果：
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/87621.html
