二分查找概述
首先, 假设表中元素是按升序排列, 将表中间位置记录的关键字与查找关键字比较, 如果两者相等, 则查找成功; 否则利用中间位置记录将表分成前, 后两个子表, 如果中间位置记录的关键字大于查找关键字, 则进一步查找前一子表, 否则进一步查找后一子表. 重复以上过程, 直到找到满足条件的记录, 使查找成功, 或直到子表不存在为止, 此时查找不成功.
流程分析
只根据上面的文字未免有点难以理解, 下面画个图举个例子介绍下:
二分查找的条件
顺序存储结构
按关键字大小有序排列
算法
算法如下:
package com.company;
public class BinarySearch {
public static int binarySearch(Integer[] srcArray, int des) {
int low = 0;
int high = srcArray.length - 1;
while (low <= high) {
int middle = (high + low) >>> 1;
if (des == srcArray[middle]) {
return middle;
} else if (des < srcArray[middle]) {
high = middle - 1;
} else {
low = middle + 1;
}
}
return -1;
}
public static void main(String[] args) {
Integer[] arr = {1,2,3,4,5,6,7};
int index = binarySearch(arr, 9);
System.out.println(index);// 输出 - 1
}
}
注意点:
>>> 是位运算符, 将二进制右移 1 位, 相当于除以 2, 具体如下图所示:
[图片上传失败...(image-92f4c6-1517130345291)]
计算机中数值都是用补码表示, 补码的计算方式如下:
正数的补码: 与原码相同
负数的补码: 除符号位外取反 + 1
如 - 7 的补码:
因为是负数, 则符号位为 1
原码: 10000111
-> 取反 11111000-> 加 1 11111001
来源: http://www.jianshu.com/p/7cc87bef4f66