引言
假如给你一个有序数组，然后给你一个数，让你去数组中找出该元素。如果数组中存在该元素，则返回该数在数组中的下标，如果不存在则返回-1。
如果是你，你会怎么做？给你三秒钟时间考虑，1、2、3，时间到。
是顺序查找吗？写一个循环，遍历整个数组去和目标数比较？那如果数据量很大，而且需找到的数在数组的最后面，那是不是太慢了？比如一个从0开始到9999的数组，我要查找9999这个数，是不是要比较9999+1次，才能得出9999所在的下标？有没有更简单的方法找出？
有，不要忘记我们的另一个条件，数组是有序的，对于有序的数组我们可以使用二分查找，又称对半查找、折半查找等等，虽然别名很多，但实现原理都是一样的。
什么是二分
二分查找，顾名思义，这种算法的精髓就在于二分，那什么是二分？它又是怎么实现二分的呢？
二分的定义及二分查找算法的思路
二分定义
二分就是每次把当前需要寻找的数组分成两半，那么我需要寻找的这个数只可能在左半边，或者右半边，这样一来我每次分完，所需要查找的元素的个数就是上一次查找元素个数的一半。
比如[1 ,4, 9, 15, 27, 49, 128, 157]这个数组，我第一次把元素以27为中点，分为左边4个，右边3个。然后再查找，我们以左边为例，左边4个元素我们以9为中点分割，分为左边2两个元素，右边一个元素。。。。直至分割到元素只有一个时结束。
二分查找算法的思路
二分查代码具体实现
伪代码
/* * 二分查找 * arr输入数组 * x目标值 * left二分左边界 * right二分右侧边界 */ public static int binarySearch(int[] arr, int target , int left , int right) {
//判断是否已经到达出口--即元素不存在当前需判断的数组元素中 //找出中间的值的下标 //判断目标值在当前值的左侧还是右侧 //在左侧则对左侧执行二分法查找 //在右侧则对右侧执行二分法查找 //若当前中点值就是目标值则结束方法 返回结果 } 实现代码
/* * 二分查找 * arr输入数组 * x目标值 * left二分左边界 * right二分右侧边界 */ public static int binarySearch(int[] arr, int target , int left , int right) {
/* * 目标值比最左侧的小 或者 比如数组为[1,6,9,14] 找-1 就会结束查找 * 目标值比最右侧的大 或者 比如数组为[1,6,9,14] 找18 就会结束查找 * 左侧下标大于右侧下标 比如数组为[1,6,9,14] 找4 就会结束查找 * */ //判断是否已经到达出口--即元素不存在当前需判断的数组元素中 if(target < arr[left] || target > arr[right] || left > right){
return -1; } //找出中间的值的下标 int mid = (left + right)/2; //判断目标值在当前值的左侧还是右侧 if(arr[mid] > target && left <= right) {
//递归左侧 return binarySearch(arr,target , left , mid-1); }else if(arr[mid] < target && left <= right) {
//递归右侧 return binarySearch(arr,target, mid+1 , right); }else {
//目标值与中点值相等 return mid; } } 版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/219854.html原文链接：https://javaforall.net
