原创 二分法检索变种实现代码怎么写？

　　二分法检索变种实现代码怎么写？二分法中每次排除都可以排除掉一半的情况，这样寻找效率很高。之所以叫二分，因为每次排除都把所有的情况分成"可能"和"不可能"两种,然后抛弃所有"不可能"的情况。

　　二分法真的不简单，尤其是二分法的各个变种。最简单的二分法，就是从一个排好序的数组之查找一个key值。如下面的程序：

　　这个程序，相信只要是一个合格的程序员应该都会写。稍微注意一点， 每次移动left和right指针的时候，需要在mid的基础上+1或者-1， 防止出现死循环， 程序也就能够正确的运行。

　　但如果条件稍微变化一下， 你还会写吗？如，数组之中的数据可能可以重复，要求返回匹配的数据的最小（或最大）的下标；更近一步， 需要找出数组中第一个大于key的元素（也就是最小的大于key的元素的）下标，等等。这些，虽然只有一点点的变化，实现的时候确实要更加的细心。下面列出了这些二分检索变种的实现。

　　1、找出第一个与key相等的元素

　　2、找出最后一个与key相等的元素

　　3、查找第一个等于或者大于Key的元素

　　4、查找第一个大于key的元素

　　5、查找最后一个等于或者小于key的元素

　　6、查找最后一个小于key的元素

      总结：
　　算法：当数据量很大适宜采用该方法。采用二分法查找时，数据需是排好序的。
　　基本思想：假设数据是按升序排序的，对于给定值key，从序列的中间位置k开始比较，
　　如果当前位置arr[k]值等于key，则查找成功；
　　若key小于当前位置值arr[k]，则在数列的前半段中查找,arr[low,mid-1]；
　　若key大于当前位置值arr[k]，则在数列的后半段中继续查找arr[mid+1,high]，
　　直到找到为止,时间复杂度:O(log(n))。