刷题时，对二分查找的各种应用情况不太熟悉，严重影响了做题速度，特此总结下。在知乎上有一篇关于较全面的二叉查找，参考链接如下：【二分查找有几种写法？它们的区别是什么？】
综上所述，二分查找共有 2×4×8=64 种写法。接下来，我们就分别实现下，上述各种版本。
向下取整的核心代码为int mid = lf + (rt - lf) /2;，简单列一个表格，说明向下取整。
当数组长度为奇数的情况时:
index012345678910len1234567891011 int lf = 0, rt = len - 1; // lf = 0, rt = 10 int mid = lf + (rt - lf) / 2; // mid = 5 整除当数组长度为偶数的情况时:
index01234567891011len123456789101112 int lf = 0, rt = len - 1; // lf = 0, rt = 11 int mid = lf + (rt - lf) / 2; // mid = 5 向下取整测试结果：
非重复元素
int[] nums = {1,2,3,4,5,6,7,8,9,10}; for (int i = 0; i < nums.length; i++){ System.out.print(bs.binarySearch_1(nums,nums[i]) + " "); } int NONE = -1; System.out.println(bs.binarySearch_1(nums,NONE)); 输出： 0 1 2 3 4 5 6 7 8 9 -1重复元素
// 重复元素 int[] nums_repeated = {1,2,3,4,5,5,6,6,7,8,9,10}; for (int i = 0; i < nums_repeated.length; i++){ System.out.print(bs.binarySearch_1(nums_repeated,nums_repeated[i]) + " "); } System.out.println(bs.binarySearch_1(nums,NONE)); 输出： 0 1 2 3 4 4 6 6 8 9 10 11 -1为什么是lf < rt，能不能lf <= rt？ 不能，注意while循环中的判断语句，砍掉的元素一定是小于key的，如果元素不重复好办，当小于key的元素坎完后，就可以接着坎key的右半部分，由向下取整决定，每当坎一次右，rt向左移动一格，直到lf == rt，此时必须跳出循环，如果改成 lf <= rt，那么必然会进入死循环。
while循环外部为什么还需要判断一次？ 小于key的左半部分一定是被砍掉的，但while循环中被砍掉最后一个元素跳出循环后，它可能有两种情况，key 和比key大的值，所以必须进行一次判断。
测试结果：
// 对于不下降序列a，求最小的i，使得a[i] > key int[] nums_2 = {1,2,3,4,5,6,7,8,9,10}; for(int i = 0; i < nums_2.length; i++){ System.out.print(bs.binarySearch_2(nums_2, nums_2[i]) + " "); } 输出： 1 2 3 4 5 6 7 8 9 -1 循环外的if语句是否可以去掉，直接返回rt？ 你可以试试，用我的测试用例重新跑一下，你就发现问题了。这里就是为了防止边界条件而进行的约束，假设lf在不断更新，导致的一个结果就是它将不断靠近rt而rt始终没有变化，此处如果遍历到数组末端那个元素，它会同样跳出循环，而让它跳出的是while循环中的if语句，而非else，所以while循环的判断语句是为了规避这种特殊情况。向下取整的核心代码为int mid = lf + (rt + 1 - lf) /2;，简单列一个表格，说明向上取整。
当数组长度为奇数的情况时:
index012345678910len1234567891011 int lf = 0, rt = len - 1; // lf = 0, rt = 10 int mid = lf + (rt + 1 - lf) / 2; // mid = 5 不影响当数组长度为偶数的情况时:
index01234567891011len123456789101112 int lf = 0, rt = len - 1; // lf = 0, rt = 11 int mid = lf + (rt + 1 - lf) / 2; // mid = 6 向上取整此处和向下取整，求最小的i是一个完美对偶关系，显然用向上取整的方式更容易实现，代码如下。
/** * 对于不下降序列a，求最大的i，使得a[i] = key * @param nums * @param key * @return */ public int binarySearch_3(int[] nums, int key){ int lf = 0, rt = nums.length-1; while (lf < rt){ int mid = lf + (rt + 1 - lf) / 2; if (nums[mid] > key){ rt = mid -1; }else{ lf = mid; } } if(nums[lf] == key) return lf; return -1; }测试结果：
非重复元素
// 非重复元素 for (int i = 0; i < nums.length; i++){ System.out.print(bs.binarySearch_3(nums,nums[i]) + " "); } System.out.println(bs.binarySearch_3(nums,NONE)); 输出： 0 1 2 3 4 5 6 7 8 9 -1重复元素
// 重复元素 for (int i = 0; i < nums_repeated.length; i++){ System.out.print(bs.binarySearch_3(nums_repeated,nums_repeated[i]) + " "); } System.out.println(bs.binarySearch_3(nums,NONE)); 输出： 0 1 2 3 5 5 7 7 8 9 10 11 -1是不是很有爱，向上取整能够取重复元素的最大下标！而且代码形式和向下取整的最小i完美对称。
同样的，因为while循环中的主要变动在于rt指针，把所有大于key的元素全部砍掉，而一旦所有元素符合小于等于key的条件时，由于向上取整的好处，lf指针也会慢慢向rt靠近，所以针对重复元素它选取的一定是最大下标。
测试结果：
// 对于不下降序列a，求最大的i，使得a[i] < key for(int i = 0; i < nums_2.length; i++){ System.out.print(bs.binarySearch_4(nums_2, nums_2[i]) + " "); } 输出： -1 0 1 2 3 4 5 6 7 8和向下取整求最小的i，一个道理，最坏情况rt不断递减地靠近lf，此时对于第一个元素会存在漏检的情况，所以最后要加一个边界条件。
