你确定你真的会二分查找算法么
引子
我记得我在京东的时候，面试过大概10个候选人，当我问到算法的时候，大部分人说我只会写简单的排序算法和二分查找之类的算法。
其实，我先不说排序算法就有十多种，二分查找，你确定你真的会么？
原理很简单，细节是魔鬼。
详解
所谓二分查找算法是针对一个排序数组的，因为数组有顺序且有固定的索引，所以你可以运用这种折半查找的算法，它的原理有点类似我们玩的一种猜数字的游戏。
就是我心中默想一个数字，你说一个数，我告诉你是大了还是小了，那么怎么猜效率才最高呢？那就是每次取中间的数字猜，一次就排出掉剩余答案的一半，这样就算有1024个数字，你也只需要10次就可以了，因为2的10次方等于1024，这种对数阶的时间复杂度有时候比常数阶都可怕，因为这个常数可能是1000，因为次数是确定的，也会被认为是常数阶。
那么，二分查找算法要怎么写，我相信绝大多数的人都能写出来以下这段代码。
private static int bSearch1(int[] arr, int target) {int left = 0;int right = arr.length - 1;while (left <= right) {int mid = left + ((right - left) >> 1);if (arr[mid] < target) {left = mid + 1;continue;}if (arr[mid] > target) {right = mid - 1;continue;}return mid;}return -1;}
上面这段代码也许就是大部分眼里的二分查找算法，当然其中有很多细节要注意。left <= right啊，计算两个数字的中间值int mid = left + ((right - left) >> 1); 这样可以避免当数字过大发生超出int承受的最大值的情况啊。
在我面试的时候，确实很多面试者也是给出了这个答案。那我会接着问，那你知道你这种写法适合什么场景么？
这种写法适合排序数组的数据不重复的时候。
那么还有什么情况呢？
我先把问题抛给大家，大家可以思考一下。
* 如果数组的数据有重复，我想找第一个。
* 如果数组的数据有重复，我想找最后一个。
* 我要找数组里面第一个不小于给定数字的。
* 我要找数组里面最后一个不大于给定数字的。
来吧，看看有多少人能一次性都写出来了，请在评论区告诉我，至少京东的那几个面试者，在我规定的10分钟里，都没有写出来。
有重复数据寻找第一个相等的值
第一种变形，我们要找第一个的话，当我们找到了相等的时候，要判断一下，这个数字是不是在索引0 的位置，然后它前面的数字是不是小于给定的数字，二者满足其一，才是正确的答案，否则right指针要继续指向mid - 1。
/*** 有重复数据寻找第一个相等的值*/private static int bSearch2(int[] arr, int target) {int left = 0;int right = arr.length - 1;while (left <= right) {int mid = left + ((right - left) >> 1);if (arr[mid] > target) {right = mid - 1;continue;}if (arr[mid] < target) {left = mid + 1;continue;}if (mid == 0 || arr[mid - 1] != target) {return mid;}right = mid - 1;}return -1;}
有重复数据寻找最后一个相等的值
第二种变形，当我们找到相等的之后，我们要判断一下这个元素是不是在数组的最后，他后面的元素是不是大于给定元素，二者满足其一才返回，否则left节点要指向mid + 1。
/*** 有重复数据寻找最后一个相等的值*/private static int bSearch3(int[] arr, int target) {int left = 0;int right = arr.length - 1;while (left <= right) {int mid = left + ((right - left) >> 1);if (arr[mid] > target) {right = mid - 1;continue;}if (arr[mid] < target) {left = mid + 1;continue;}if (mid == arr.length - 1 || arr[mid + 1] != target) {return mid;}left = mid + 1;}return -1;}
第一个不小于给定值的数据
第三种变形，如果找到一个数值大于给定数值，要判断是不是索引为0，然后前面的数字数不是小于给定数值，满足其一，返回，否则right指针要指向mid - 1。
private static int bSearch4(int[] arr, int target) {int left = 0;int right = arr.length - 1;while (left <= right) {int mid = left + ((right - left) >> 1);if (arr[mid] >= target) {if (mid == 0 || arr[mid - 1] < target) {return mid;}right = mid - 1;continue;}left = mid + 1;}return -1;}
最后一个不大于给定值的数据
第四种变形，如果找到一个数字小于给定数字，那么要看这个数字是不是在数组的最后，然后后面的数字是不是大于给定数值，二者满足其一，返回，否则left指针要指向mid + 1。
/*** 找最后一个不大于给定值的数据*/private static int bSearch5(int[] arr, int target) {int left = 0;int right = arr.length - 1;while (left <= right) {int mid = left + ((right - left) >> 1);if (arr[mid] <= target) {if (mid == arr.length - 1 || arr[mid + 1] > target) {return mid;}left = mid + 1;continue;}right = mid - 1;}return -1;}
最后
这五种都自己写出来了，再和面试官说我会二分查找算法，哈哈。
我是大航子，完整的代码如下，拿走不谢。
package com.example.demo.rob;public class BSearch {public static void main(String[] args) {System.out.println(bSearch5(new int[]{1, 1, 1, 3, 4}, 4));}/*** 数据不重复*/private static int bSearch1(int[] arr, int target) {int left = 0;int right = arr.length - 1;while (left <= right) {int mid = left + ((right - left) >> 1);if (arr[mid] < target) {left = mid + 1;continue;}if (arr[mid] > target) {right = mid - 1;continue;}return mid;}return -1;}/*** 有重复数据寻找第一个相等的值*/private static int bSearch2(int[] arr, int target) {int left = 0;int right = arr.length - 1;while (left <= right) {int mid = left + ((right - left) >> 1);if (arr[mid] > target) {right = mid - 1;continue;}if (arr[mid] < target) {left = mid + 1;continue;}if (mid == 0 || arr[mid - 1] != target) {return mid;}right = mid - 1;}return -1;}/*** 有重复数据寻找最后一个相等的值*/private static int bSearch3(int[] arr, int target) {int left = 0;int right = arr.length - 1;while (left <= right) {int mid = left + ((right - left) >> 1);if (arr[mid] > target) {right = mid - 1;continue;}if (arr[mid] < target) {left = mid + 1;continue;}if (mid == arr.length - 1 || arr[mid + 1] != target) {return mid;}left = mid + 1;}return -1;}/*** 找第一个不小于给定值的数据*/private static int bSearch4(int[] arr, int target) {int left = 0;int right = arr.length - 1;while (left <= right) {int mid = left + ((right - left) >> 1);if (arr[mid] >= target) {if (mid == 0 || arr[mid - 1] < target) {return mid;}right = mid - 1;continue;}left = mid + 1;}return -1;}/*** 找最后一个不大于给定值的数据*/private static int bSearch5(int[] arr, int target) {int left = 0;int right = arr.length - 1;while (left <= right) {int mid = left + ((right - left) >> 1);if (arr[mid] <= target) {if (mid == arr.length - 1 || arr[mid + 1] > target) {return mid;}left = mid + 1;continue;}right = mid - 1;}return -1;}}