java 二分算法_Java实现的二分查找算法

二分查找过程

二分查找，也称折半查找，是对有序序列的查找算法，时间复杂度为O(log n).本文的重点是某元素二分查找的比较次数。特别要注意的是查找的上下边界问题(下面有解释)

例：22 34 55 77 89 93 99 102 120 140，查找77需要查找的次数是多少？

答：4次。

序列： 22 34 55 77 89 93 99 102 120 140

下标：0 1 2 3 4 5 6 7 8 9

用low表示低位元素下标，用high表示高位下标

查找77

第一次查找：(low+high)/2 = (0+9)/2 = 4 ,查找下标为4的元素，即89。由于89>77，在89的左侧继续查找。此时调整low=0,high=3

请注意，由于知道下标为4的元素89比要查找的元素77大，为了提高效率，会跳过下标为4的元素，使得high=3

第二次查找：(low+high)/2=(0+3)/2=1,查找下标为1的元素，即34。由于34<77，因此，在34的右侧继续查找。此时调整low=2,high=3,由于已知道1号元素34与77不相等，所以low不取1。

第三次查找：(low+high)/2=(2+3)/2=2,查找下标为2的元素，即55。由于55<77，在55的右侧继续查找。此时调整low=3,high=3.low取3而不取2的原因同上。

第四次查找：(low+high)/2=(3+3)/2=3,查找下标为3的元素，即77. 77=77,找到目标元素，查找结束。

同理查找34和99,需要比较的次数分别是2和4次

/** BinarySearch.java

* Version 1.0.0

* Created on 2017年12月17日

* Copyright ReYo.Cn*/

packagereyo.sdk.utils.test.search;/*** 创 建 人：AdministratorReyoAut

* 创建时间：2017年12月17日 上午10:06:08

*

*@authorReYo

*@version1.0*/

/*** 二分查找又称折半查找，它是一种效率较高的查找方法。

【二分查找要求】：1.必须采用顺序存储结构 2.必须按关键字大小有序排列。**/

public classBinarySearch {public static voidmain(String[] args) {int[] src = new int[] { 1, 3, 5, 7, 8, 9};

System.out.println(binarySearch(src,3));

System.out.println(binarySearch(src,3, 0, src.length - 1));

}/*** * 二分查找算法 * *

*

*@paramsrcArray

* 有序数组 *

*@paramdes

* 查找元素 *

*@returndes的数组下标，没找到返回-1*/

public static int binarySearch(int[] srcArray, intdes) {int low = 0;int high = srcArray.length - 1;while (low <=high) {int middle = (low + high) / 2;if (des ==srcArray[middle]) {returnmiddle;

}else if (des

high= middle - 1;

}else{

low= middle + 1;

}

}return -1;

}/***二分查找特定整数在整型数组中的位置(递归)

*@paramdataset

*@paramdata

*@parambeginIndex

*@paramendIndex

*@returnindex*/

public static int binarySearch(int[] dataset, int data, int beginIndex, intendIndex) {int midIndex = (beginIndex + endIndex) / 2;if (data < dataset[beginIndex] || data > dataset[endIndex] || beginIndex >endIndex) {return -1;

}if (data

}else if (data >dataset[midIndex]) {return binarySearch(dataset, data, midIndex + 1, endIndex);

}else{returnmidIndex;

}

}

}

其它方式的思考：

问题：   某数组A[1..n]含有所有从0..n的所有整数，但其中有一个整数不在数组中，通过利用一个辅助数组B[0..n]来记录A中出现的整数，很容易在 O(n)时间内找出所缺的整数。但在这个问题中，我们却不能由一个单一操作来访问A中的一个完整整数，因为A中元素是以二进制表示的。我们所能用的唯一操 作就是“取A[i]的第j位”这个操作所花时间为常数。

证明：如果访问数组A中信息的唯一方式是这种单一位操作，仍能在O(n)时间内找出所缺的整数。A之外的任一完整整数仍然可以由一个单一操作来访问。

基本方法就是用二分法：

1, 遍历整数0到n的第一位，分成两个数组：P1[1] 和P0[1]，分别代表第一位是1，0的数，并记录第一位是1的个数CountN，代价为O(n)

2, 遍历数组A[1...n]的第一位, 分成两个组：Q1[1]和Q0[1]，分别代表第一位是1，0的数，并记录1的个数CountA，代价为O(n)

3, 比较CountN和CountA的值，结果可能有两种情况CountN = CountA，或者CountN = CountA + 1， 前者表明所缺数的第一位为0， 后者为1，代价为O(1)

4,

通过3的结果，随后我们可以在P1[1]和Q1[1](CountN>CountA，即缺少第一位为1的数)  或者

P0[1]和Q0[1](CountN=CountA，即缺少第一位为0的数)中的第2位中重复步骤1，2中的操作，记录数组P1[2]、P0[2]和

CountN'及Q1[2]、Q0[2]和CountA'。代价为O(n/2)和O(n/2),

经过比较后可得到所缺数第二位是0还是1，决定接下来比较P1[2]和Q1[2]  或者 P0[2]和Q0[2]，代价O(1)

5, 不断重复Ceiling(lg(n))次，最后即可找到所缺数总代价为2* (O(n) + O(n/2) + ... +O(n/pow(2, k))) + ... + O(1)) = 2* O(2n) = 4*O(n) = O(n)

当然这里忽略了一个问题，如果A中缺了一个，这应该是n-1个数，则多出来的那个数是什么呢，如果和其他数有重复，上面的方法就无效了，情况变得相当复杂。因此上面的只适用于多出的一个数为0，或者干脆就只有n-1个数。

【另】

比较弱的方法：1到n所有数字加起来的和 减去 A[1]到A[n]的和

比较犀利的方法：凑m，m=4k-1,并且是4k-1>=n的最大整数(比如n=7，则m=7；n=16，则m=19；n=21，m=23以此类推)

那么只需要A[1]^A[2]^……^A[n-1]^A[n]^{A[m-2]^A[m-1]^A[m]}，即可

原因：从4的整数倍开始，连续4个数字异或，结果为(例如4^5^6^7的结果是0；204^205^206 = 207；8^10^11=9)

所以0^1^2^……^m的结果为0，却哪个数字，则A[1]^A[2]^……^A[n-1]^A[n]^{A[m-2]^A[m-1]^A[m]}的结果就是所缺的数字