Java 算法的二分法

本文主要是介绍Java 算法的二分法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.原理

1.1.在升序的集合中对半查找中位的下标，如果中位的下标和要查找的下标相等时，找到目标数，那二分结束。
1.2.如果 集合[中位]大于查找值，说明查找值在中位的左边，那么高位就是此时的中位-1，然后继续二分
1.3.如果集合[中位]小于查找值，说明查找值在中位的右边，那么低位就是此时的中位+1，然后继续二分
1.4.如果低位下标大于高位下标，那就没有找到值

2.实例

/*** @ClassName BinarySearchDemo* @Description TODO* @date 2020/8/28 11:29* @Version 1.0*/
public class BinarySearchDemo {int[] array = null;/*** @Author: djz* @Description: 初始化一个集合* @DateTime: 2020/8/28 13:55* @Params:* @Return*/public void init() {//1-100---用二分法，集合需要是有顺序的array = new int[100];for (int i = 0; i < array.length; i++) {array[i] = i + 1;}}/*** @Author: djz* @Description: 正常方法* @DateTime: 2020/8/28 13:41* @Params: * @Return */public void normalFor(int num) {System.out.println("**********normalFor*************");boolean isExist=false;int count=0;for (int i = 0; i < array.length; i++) {count++;if (num == array[i]) {isExist=true;System.out.println("在数组下标为" + i + "的地方找到值"+num+"，查找了" + count + "次。");break;}}if(!isExist)System.out.println(num + "没找到了");}/*** @Author: djz* @Description: for循环的二分法* @DateTime: 2020/8/28 13:54* @Params:* @Return*/public void binarySearchFor(int num) {System.out.println("**********binarySearchFor*************");int low = 0; // 检索的时候int high = array.length - 1;  //用start和end两个索引控制它的查询范围int mid = 0;int count = 0;boolean isExist=false;for (int i = 0; i < array.length; i++) {count++;mid = (low + high) / 2;if (array[mid] < num) {low = mid+1;} else if (array[mid] > num) {high = mid-1;} else {isExist=true;System.out.println("在数组下标为" + mid + "的地方找到值"+num+",查找了" + count + "次。");break;}}if(!isExist)System.out.println(num + "没找到了");}/*** @Author: djz* @Description: while循环的二分法* @DateTime: 2020/8/28 13:55* @Params:* @Return*/public void binarySearchWhile(int num) {System.out.println("**********binarySearchWhile*************");int low = 0;//低位int high = array.length - 1;//高位int mid = 0;//中间值下标，中位int count=0;//计算次数boolean isExist=false;//低位不大于高位while (low <= high) {count++;//二分后有三种情况：array[mid]比num值大；array[mid]比num值小；array[mid]和num值相等mid = (low + high) / 2;//二分之后中位比num值大，说明num值在中位的右边，那么高位就是此时的中位，然后继续二分if (array[mid] > num) {high = mid - 1;}//二分之后中位比num值小，说明num值在中位的左边，那么低位就是此时的中位，然后继续二分else if (array[mid] < num) {low = mid + 1;}else{isExist=true;System.out.println("在数组下标为" + mid + "的地方找到值"+num+",查找了" + count + "次。");break;}}if (!isExist)System.out.println(num + "没找到了");}public static void main(String[] args) {BinarySearchDemo binarySearchDemo = new BinarySearchDemo();binarySearchDemo.init();int num = 99;binarySearchDemo.normalFor(num);binarySearchDemo.binarySearchFor(num);binarySearchDemo.binarySearchWhile(num);}}

3.结果

**********normalFor*************
99找到了，在数组下标为98的地方，查找了99次。
**********binarySearchFor*************
在数组下标为98的地方找到值99,查找了6次。
**********binarySearchWhile*************
在数组下标为98的地方找到值99,查找了6次。

4.二分法的查找次数

对于包含n个元素的列表，用二分查找最多需要log2^n步，而简单查找最多需要n步。
如果在1024个元素中找一个数，最多是log2^1024=10 (1024=2^10)
2^1=2
2^2=4
2^3=8
2^4=16
2^5=32
2^6=64
2^7=128
2^8=256
2^9=512
2^10=1024 1024为列表个数 10就是次数
2^11=2048
2^12=4096

这篇关于Java 算法的二分法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---