一、定义
二分查找（Binary Search）算法，也叫折半查找算法。
当我们要从一个序列中查找一个元素的时候，二分查找是一种非常快速的查找算法。
二分查找是针对有序数据集合的查找算法，如果是无序数据集合就用遍历查找。
二、本质
二分查找之所以快速，是因为它在匹配不成功的时候，每次都能排除剩余元素中一半的元素。
因此可能包含目标元素的有效范围就收缩得很快，而不像顺序查找那样，每次仅能排除一个元素。
三、思路
二分查找针对的是一个有序的数据集合，查找思想有点类似分治思想。
每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为0。
三、案例
1、一个有序的数组中查找某个数字是否存在
/**
* 二分法 标准
*/
public class HalfDemo1 {
public static int binarySearch(int[] nums, int t) {
//低位索引
int low = 0;
//高位索引
int high = nums.length - 1;
//中间索引
int mid = 0;
while (low <= high) {
// 使用（low+high）/2的话，如果low和high比较大，两者之和可能溢出
// 除以2换成位运算>>1，可以提高效率
mid = low + ((high - low) >> 1);
//等于半数
if (t == nums[mid]) {
return mid;
}
//半数以里
else if (t < nums[mid]) {
high = mid - 1;
}
//半数以外
else {
low = mid + 1;
}
}
return -1;
}
public static void main(String[] args) {
//有序数组
int[] nums = {3, 12, 24, 31, 46, 48, 52, 66, 69, 79, 82};
System.out.println(binarySearch(nums, 66));
}
}
/*
递归实现
*/
// 二分查找的递归实现
public int bsearch(int[] a, int n, int val) {
return bsearchInternally(a, 0, n - 1, val);
}
private int bsearchInternally(int[] a, int low, int high, int value) {
if (low > high) return -1;
int mid = low + ((high - low) >> 1);
if (a[mid] == value) {
return mid;
} else if (a[mid] < value) {
return bsearchInternally(a, mid + 1, high, value);
} else {
return bsearchInternally(a, low, mid - 1, value);
}
}
四、局限性
1、首先，二分查找依赖的是顺序表结构，简单点说就是数组。
因为二分查找算法需要按照下标随机访问元素。
数组按照下标随机访问数据的时间复杂度是O(1)，
而链表随机访问的时间复杂度是O(n)。
2、其次，二分查找针对的是有序数据。
如果数据没有序，我们需要先排序。
3、再次，数据量太小不适合二分查找。
如果要处理的数据量很小，完全没有必要用二分查找，顺序遍历就足够了。比如我们在一个大小为10的数组中查找一个元素，不管用二分查找还是顺序遍历，查找速度都差不多。只有数据量比较大的时候，二分查找的优势才会比较明显。
4、最后，数据量太大也不适合二分查找。
二分查找的底层需要依赖数组这种数据结构，而数组为了支持随机访问的特性，要求内存空间连续，对内存的要求比较苛刻。比如，我们有1GB大小的数据，如果希望用数组来存储，那就需要1GB的连续内存空间。
五、应用
1、如何设计数据结构和算法，快速判断某个整数是否出现在这1000万数据中？ 我们希望这个功能不要占用太多的内存空间，最多不要超过100MB。
每个数据大小是8字节，最简单的办法就是将数据存储在数组中，内存占用差不多是80MB，符合内存限制。
我们可以先对这1000万数据从小到大排序，然后再利用二分查找算法，
就可以快速地查找想要的数据了。