算法二分查找的变种以及注意事项

女爷i 2022-06-09 09:38 184阅读 0赞

# 二分查找 #

普通的二分查找

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

## 变种 ##

1.找到第一个等于key的元素

//找到第一个等于key的元素下标
    public static int bSearchFirstEquals(int[] array, int key) {
         int low = 0, high = array.length-1;
         int mid;
         while (low <= high) {
             mid = low + (high - low) / 2;
             if (array[mid] >= key) {
                 high = mid - 1;
             } else {
                 low = mid + 1;
             }
         }
         if (low < array.length && array[low] == key) {
             return low;
         }
         return -1;
     }

2.返回最后一个等于key元素下标

public static int bSearchLastEquals(int[] array, int key) {
        int low = 0, high = array.length - 1;
        int mid;
        while (low <= high) {
            mid = low + (high - low) / 2;
            if (array[mid] > key) {
                high = mid - 1;
            } else {
       //如果array[mid]==key也会在后一半元素中查找
                low = mid + 1;
            }
        }
        if (high < array.length && array[high] == key) {
            return high;
        }
        return -1;
    }

3.最后一个小于等于key的元素

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

4.第一个大于key的元素

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

需要注意的几点:

1.  使用递归的话要记得判断low和high是否合法 增强代码的鲁棒性
2.  一般不建议使用递归实现 原因是存在压栈和出栈的消耗
3.  对于中间值mid的计算 如果使用`mid=(low+high)/2` 存在极端情况下low+high的结果溢出，因此使用`mid=low+(high-low)/2` 更好