Java 实现二分查找（附代码及简单讲解） |
您所在的位置：网站首页 › java中的查找算法 › Java 实现二分查找（附代码及简单讲解） |
|
前言
要实现二分查找，有一个前提： 所要查找的列表必须是有序排列的，顺序排列或逆序排列。 实现源码： public class BinarySearch { public static void main(String[] args) { int[] arr = new int[] {-98,-34,2,34,54,66,79,105,201,333};//该列表顺序排序 int findNum = 34;//要查找的数据 int head = 0; int end = arr.length -1; int middle = 0; boolean isFlag = true;//若没找到，通过该bool变量输出未找到提示 while(head System.out.println("找到了，该数所在数组下标为：" + middle); isFlag = false; break; }else if(arr[middle] > findNum) { end = middle - 1; }else { head = middle + 1; } } if(isFlag) { System.out.println("很抱歉，没找到"); } } } 解释以该顺序列表为例，head为查找区间最左端，end为查找区间最右端,middle为查找区间中间部位。 如果 arr[middle] > findNum； 就代表所要查找的数在middle的左边位置，所以将end = middle - 1;因为middle所对应的数已经被检测了不是我们要找的数，所以end不能等于middle，要为end = middle - 1; 如果 arr[middle] < findNum; 就代表所要查找的数在middle的右边位置，所以将head = middle + 1;理由同上 跳出循环的条件是head > end，当head > end时，就表明已经将所有可能查到该数的区间全部查找了一遍，还没有找到该数，所以跳出循环。 为何head 会大于 end？倘若查找的数不存在，middle 、head 、end三个数最终会相等，如果该数是不存在的话，那么arr[middle]必然会大于或小于所要查找数，如果大于要查找的数，end = middle - 1;如果小于要查找的数，head = middle + 1;可见，不管如何，head是一定会大于end的，由此可以将head > end作为循环结束的条件。 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |