Java实现二分法检索算法
算法
如果给定组的数目为3、12、24、36、55、68、75、88，则检查给定值24。 三个变量front、mid和end分别指向数据的上界、中界和下界，可以是mid=(front end )/2。
如果front=0(指向3 )，end=7)指向88 )，则为mid=3)指向36 )。 因为是midx，所以应该在前半部分找。
如果新的end=mid-1=2且front=0，则新的mid=1。 在这种情况下，因为是xmid，所以确定应该在后半部分查找。
若设新的front=mid 1=2，且end=2，则新的mid=2，此时a[mid]=x，发现成功。 在要搜索的次数不是数列中的次数的情况下，例如，在x=25的情况下，在第三次判断时，xa[mid]根据上述规则设为front=mid 1，即front=3，在出现frontend的情况下，检索不成功
示例：在具有规则n个元素的数组中搜索用户输入的数据x。 算法如下。
确定搜索范围front=0，end=N-1，计算中项mid=(front end )/2。
如果a[mid]=x或front=end，则结束搜索； 否则，继续往下。
a[mid]x表示要搜索的元素的值仅在小于中项元素的范围内，将mid-1的值分配给结束，重新计算mid，并转移到步骤2。
[一维数组、混叠搜索]2算法的复杂度分析
时间的复杂性
1 .在最坏的情况下，由于要查找最后的元素(或第一个元素) Master定理t(n )=t ) n/2 (o )1)，所以t ) n )=o ) logn )
2 .用中间元素o(1)寻找的元素最好是中间元素(奇数长度数列中间，偶数长度数列中间偏左元素) )。
空间复杂性：
s(n )=n
Java实现代码
package com.leo.kang.interview；
公共类二进制搜索{
//检索次数
静态输入计数；
//*
* @param args
*/
publicstaticvoidmain (字符串[ ] args ) {
//todo自动- generated method stub
int [ ] array={ 1，2，3，4，5，6，7，8，9，10 }；
system.out.println (搜索恢复(array，0，array.length-1，9 ) )；
system.out.println(count )；
计数=0；
system.out.println (搜索loop (array，9 )；
system.out.println(count )；
}
//*
*执行递归二分查找，并返回该值最初出现的位置
*
* @param array
*已排序数组
* @param start
*开始位置
* @param end
*结束位置
* @param findValue
*所需值
*@数组中* @return值的位置从0开始。 找不到返回-1
*/
publicstaticintsearchrecursive (int [ ] array，int start，int end，
int findValue ) {
//数组为空时，如果直接返回-1，则搜索失败
if(array==null ) {
返回- 1；
}
出局；
if (开始=结束) {
//中间位置
int middle=(开始)/1；
//中位数
int middleValue=array[middle]；
if(findvalue==middlevalue ) {
//保持中位数不变返回
返回中间；
}elseif(findvaluemiddlevalue ) )
//小于中值时在中值前查找
returnsearchrecursive (阵列，开始，中间- 1，查找值)；
} else {
//大于中值的值在中值后面查找
returnsearchrecursive (阵列，中间1，结束，查找值)；
}
} else {
返回//-1时，搜索失败
返回- 1；
}
}
//*
*重复二分搜索，返回值最初出现的位置
*
* @param array
*已排序数组
* @param findValue
*所需值
*@数组中* @return值的位置从0开始。 找不到返回-1
*/
publicstaticintsearchloop (int [ ] array，int findValue ) {
//数组为空时，如果直接返回-1，则搜索失败
if(array==null ) {
返回- 1；
}
//开始位置
int start=0；
//结束位置
int end=array.length - 1；
wile (开始=结束) {
出局；
//中间位置
int middle=(开始)/2；
//中位数
int middleValue=array[middle]；
if(findvalue==middlevalue ) {
//保持中位数不变返回
返回中间；
}elseif(findvaluemiddlevalue ) )
//小于中值时在中值前查找
end=middle - 1；
} else {
//大于中值的值在中值后面查找
开始=middle 1；
}
}
返回//-1时，搜索失败
返回- 1；
}
}