算法(二) -- 二分查找及其变形体

作者：opLW
参考：

1. 王争老师的 《数据结构与算法之美》

目录

传统二分查找
变形1：查找第一个等于给定值的元素
变形2：查找最后一个等于给定值的元素
变形3：查找第一个大于等于给定值的元素
变形4：查找第一个大于给定值的元素
变形5：查找最后一个小于等于给定值的元素
变形6：查找最后一个小于给定值的元素

1.传统二分查找

public static int binarySearch(int[] ary, int target) {
        int low = 0;
        int high = ary.length - 1;
        while (low <= high) { // ==1==
            int mid = low + (high - low >> 1); ==2==
            if (target == ary[mid]) {
                return mid;
            } else if (target > ary[mid]) {
                low = mid + 1; ==3==
            } else {
                high = mid - 1; ==3==
            }
        }
        return -1;
    }

• 注意点
  • 1 注意这里是low <= high而不是low < high
  • 2 注意这里要用int mid = low + (high - low >> 1) 而不是 int mid = (low + high) / 2。优化点1 使用low + (high - low >> 1)。当使用(low + high) / 2时，如果两个数比较大，相加可能会引起溢出；优化点2 使用>>1来代替/2，位运算更加适合计算机。同时注意(high - low >> 1)要加上括号，因为>>的优先级低于+。
  • 3注意low和high区间的变化。
• 优点
  • 查找的时间复杂度为O(logn)。这样的时间复杂度，即使在数量庞大的数据中查找也有很高的效率。
• 局限性
  • 被查找的数据本身应该是有序的，也就是说我们应该维护被查找数据的有序性。所以当数据存在频繁的插入，删除操作时，二分查找不是很合适。
  • 二分查找依赖于顺序表结构，像数组这样在连续的地址上，可使用下标随机访问的。如果是在链表上查找，那么效率会很低，跟线性查找类似。
  • 因为依赖于顺序表结构，所以需要连续的内存空间。那么当数据量很大时就不适合了，因为可能没有足够大的连续内存空间。

变形1：查找第一个等于给定值的元素

public static int BSFirstEqual(int[] ary, int target) {
        int low = 0;
        int high = ary.length - 1;
        while (low <= high) {
            int mid =  low + ((high - low) >> 1);
            if (ary[mid] > target) {
                high = mid - 1;
            } else if (ary[mid] < target) {
                low = mid + 1;
            } else { // ==4==
                if ((mid == 0) || (ary[mid - 1] != target)) return mid;
                else high = mid - 1;
            }
        }
        return -1;
    }

• ary[mid] > target和ary[mid] < target时，与传统的二分查找相似。
• 4 唯一的不同之处。因为我们要在所有数值等于给定值的元素中找到第一个，所以当ary[mid] == target时：
  • 如果mid==0，即前面没有数据了，那么这个元素就是等于给定数值的所有元素中的第一个了。
  • 如果ary[mid - 1] != target，即前一个数据不等于给定数值了，那么这个元素就是等于给定数值的所有元素中的第一个了。
  • 满足以上两个其中一个，即可返回。如果两个都不符合，那么就要high = mid - 1继续向左查找。

变形2：查找最后一个等于给定值的元素

public static int BSLastEqual(int[] ary, int target) {
        int low = 0;
        int high = ary.length - 1;
        while (low <= high) {
            int mid =  low + ((high - low) >> 1);
            if (ary[mid] > target) {
                high = mid - 1;
            } else if (ary[mid] < target) {
                low = mid + 1;
            } else {
                if ((mid == ary.length - 1) || (ary[mid + 1] != target)) return mid;
                else low = mid + 1;
            }
        }
        return -1;
    }

变形3：查找第一个大于等于给定值的元素

public static int BSFirstBigEqual(int[] ary, int target) {
        int low = 0;
        int high = ary.length - 1;
        while (low <= high) {
            int mid =  low + ((high - low) >> 1);
            if (ary[mid] >= target) {
                if ((mid == 0) || (ary[mid - 1] < target)) return mid;
                else high = mid - 1;
            } else if (ary[mid] < target) {
                low = mid + 1;
            }
        }
        return -1;
    }

• 因为是第一个大于等于给定值的元素，所以我们把大于等于集合到一块，即ary[mid] >= target。并且在其中做判断，当到mid == 0或者ary[mid - 1] < target时，停止寻找返回数据；否则继续向左查找。

变形4：查找第一个大于给定值的元素

public static int BSFirstBig(int[] ary, int target) {
        int low = 0;
        int high = ary.length - 1;
        while (low <= high) {
            int mid =  low + ((high - low) >> 1);
            if (ary[mid] > target) {
                if ((mid == 0) || (ary[mid - 1] <= target)) return mid;
                else high = mid - 1;
            } else if (ary[mid] <= target) {
                low = mid + 1;
            }
        }
        return -1;
    }

变形5：查找最后一个小于等于给定值的元素

public static int BSLastSmallEqual(int[] ary, int target) {
        int low = 0;
        int high = ary.length - 1;
        while (low <= high) {
            int mid =  low + ((high - low) >> 1);
            if (ary[mid] > target) {
                high = mid - 1;
            } else if (ary[mid] <= target) {
                if ((mid == ary.length - 1) || (ary[mid + 1] > target)) return mid;
                else low = mid + 1;
            }
        }
        return -1;
    }

变形6：查找最后一个小于给定值的元素

public static int BSLastSmall(int[] ary, int target) {
        int low = 0;
        int high = ary.length - 1;
        while (low <= high) {
            int mid =  low + ((high - low) >> 1);
            if (ary[mid] >= target) {
                high = mid - 1;
            } else if (ary[mid] < target) {
                if ((mid == ary.length - 1) || (ary[mid + 1] >= target)) return mid;
                else low = mid + 1;
            }
        }
        return -1;
    }

总结

• 其实二分查找主要分为三种情况：>,==,<。总结以上规律，我们只要根据题意在符合的情况中进行进一步的判断即可，对于其他不符合的情况按照传统的处理方式处理。特别地当符合的情况中不包含==时，我们将==和另外一种不符合要求的情况归为一类处理。下面看看具体例子。
• 例如在变形6：查找最后一个小于给定值的元素中。根据题意可知符合的情况为小于<，那么我们只需ary[mid] < target时，进行进一步的判断；而对于> ,==，我们归为同一类处理。
• 其实上面只是介绍了大体的思路，关键还在于理解吃透，再灵活应用，具体题目具体分析。

万水千山总是情，麻烦手下别留情。
如若讲得有不妥，文末留言告知我，
如若觉得还可以，收藏点赞要一起。
opLW原创七言律诗，转载请注明出处