二分查找(Binary Search)算法，也叫折半查找算法。
1.1、原理分析
二分查找是一种非常简单易懂的快速查找算法，其思想在生活中随处可见，比如朋友聚会的时候爱玩的一个猜数游戏，我随机写一个0-100之间的数字，然后大家依次来猜，猜的过程中大家每猜一次我都会告诉大家猜大了还是猜小了，直到有人猜中为止，猜中的人会有一些惩罚措施。这个过程其实就是二分查找思想的一种体现。
回到实际的开发场景中，假设有10个订单，其金额分别是：6，12，15，19，24，26，29，35，46，67。请从中找出订单金额为15的订单，利用二分查找的思想我们每次都与区间中间的数据进行大小的比较以缩小查找的范围，下面这幅图代表了查找的过程，其中 left，right代表了待查找区间的下标，mid表示待查找区间中间元素的下标(如果范围区间是偶数个导致中间数有两个就选择较小的那个)
通过这个查找过程我们可以对二分查找的思想做一个汇总：二分查找针对的是一个有序的数据集合，查找思想有点类似分治思想。每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为 0
1.2、复杂度分析
理解了二分查找的思想后我们来分析二分查找的时间复杂度，首先我们要明确二分查找是一种非常高效的查找算法，通过分析其时间复杂度我们就可以发现，我们假设数据大小为n，每次查找完后数据的大小缩减为原来的一半，直到最后数据大小被缩减为1此时停止，如果我们用数据来描述其变化的规律那就是：
n，n/2，n/4，n/8，n/16，n/32，.......................，1；
可以看出来，这是一个等比数列，当数据大小变为1时：
其中k 的值就是总共缩小的次数。而每一次缩小操作只涉及两个数据的大小比较，所以，经过了 k 次区间缩小操作，通过计算k的值我们可以得出二分查找的时间复杂度就是 O(logn)
这是一种非常高效的时间复杂度，有时候甚至比O(1)复杂度更高效，为什么这么说呢？因为对于log n来说即使n非常的大对应的log n的值也会很小，之前在学习O(1)复杂度时我们讲过O(1)代表的是一种常量级复杂度并不是说代码只需要执行一次，有时候可能要执行100次，1000次这种常数级次数的复杂度都可以用O(1)表示，所以，常量级时间复杂度的算法有时候可能还没有 O(logn) 的算法执行效率高。
1.3、代码实现
二分查找的实现方式有基于循环的实现方式，也有基于递归的方式，现给出这两种方式编写的代码模板
1、基于循环的二分查找代码模板
// 返回的是元素在数组中的下标
public int binarySearch(int[] array, int target) {
int left = 0, right = array.length - 1, mid;
while (left <= right) {
// mid = （left + right）>> 1
mid = left + ((right - left) >>1) ;
if (array[mid] == target) {
return mid;
} else if (array[mid] > target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return -1;
}
用mid不断去逼近我们的目标值，相对好的情况直接在某段中间找到了目标值，最坏的情况是不断去逼近，最后left==right找到目标值，当然如果真的找不到目标值也就是left>right的时候。
2、基于递归的二分查找代码模板
public int recurBinarySearch(int[] array, int target,int left,int right) {
//terminal
if (left > right) {
return -1;
}
//process current 计算中间元素的下标
int mid = left + ((right - left)>>1);
if (array[mid] == target) {
return mid;
}else if (array[mid] > target) {
//drill down
return recurBinarySearch(array,target,left,mid-1);
}else {
return recurBinarySearch(array,target,mid+1,right);
}
}
进阶：二分查找的实现我们可以分为两大类情况
1，有序数列中不存在重复元素的简单实现；
2：有序数列中存在重复元素的变形实现，
针对第一种，上面已经给出了代码模板，针对第二种，在实际的应用场景中可能会出现如下几种情况：
2.1、从数据序列中查找第一个值等于给定值的元素，比如在{6,12,15,19,24,26,29,29,29,67}中找第一个等于29的元素
2.2、从数据序列中查找最后一个值等于给定值的元素。还是刚刚的元素序列，找最后一个等于29的元素
2.3、从数据序列中查找第一个大于等于给定值的元素。
2.4、从数据序列中查找出最后一个值小于等于给定值的元素。
课后思考：针对这四种情况，代码应该如何实现呢？
1.4、应用场景说明
二分查找的时间复杂度是O(log n)，其效率非常高，那是不是说所有情况下都可以使用二分查找呢？下面我们讨论一下二分查找的应用前提
1、待查找的数据序列必须有序
二分查找对这一要求比较苛刻，待查找的数据序列必须是有序的（单调递增或者单调递减），假如数据无序，那我们要先排序，然后二分查找，如果我们针对的是一组固定的静态数据，也就说该数据序列不会进行插入和删除操作，那我们完全可以先排序然后二分查找，这样子一次排序多次查找；但是如果数据序列本身不是固定的静态的，可能涉及数据序列的插入和删除操作，那我们每次查找前都需要进行排序然后才能查找，这样子成本非常的高。
2、数据的存储依赖数组
待查找的数据序列需要使用数组进存储，也就是说依赖顺序存储结构。那难道不能用其他的结构来存储待查找的数据序列吗？比如使用链表来存储，答案是不可以的，通过我们前面实现的二分查找的过程可知，二分查找，算法需要根据下标，left,right,mid来访问数据序列中的元素，数组按照下标访问元素的复杂度是O(1)，而链表访问元素的时间复杂度是O(n)，因此如果使用链表来存储数据二分查找的时间复杂度就会变得很高。
3、数据序列存在上下边界
数据序列有上下边界，才能找到中间点，这样才能二分下去。
4、数据量太小或太大都不适合用二分查找
数据量很小的情况下，没有必要使用二分查找，使用循环遍历就够了，因为只有在数据量比较大的情况下二分查找才能体现出优势，不过在某些情况下即使数据量很小也建议大家使用二分查找，比如数据序列中的数据都是一些长度非常长的字符串，这些长度非常长的字符串比较起来也会非常的耗时，所以我们要尽可能的减少比较的次数，这样反倒有助于提高性能。
那为什么数据量太大的情况下也不建议使用二分查找呢？因为我们前面刚讲到二分查找底层需要依赖数组存储待查找的数据序列，而数组的特点是需要连续的内存空间，比如现在有1G的订单数据，如果用数组来存储就需要1G的连续内存，即便有