二分查找以及二分查找的变形

二分查找以及二分查找的变形

常规二分查找：在有序数组中找到num

代码：

//1.常规二分查找 首先需要保证这个数组是有序的
    //在有序数组中找到num
    public static boolean find(int[] array,int num){
        //定义一个”左指针“
        int left = 0;
        //定义一个"右指针"
        int right = array.length - 1;
        if(array == null || array.length == 0){
            return false;
        }
        //当左指针<=右指针的时候进行二分查找
        while (left <= right){
            //定义一个中间节点
            int mid = (left + right) / 2;
            if(array[mid] == num){
                return true;
            }else if (array[mid] > num){
                right = mid - 1;
            }else if (array[mid] < num){
                left = mid + 1;
            }
        }
        //证明没有找到这个元素
        return false;
    }

非常规二分查找：找到数组中>=num最左的位置

代码：

 //2.二分查找的变形
    //在数组中找到>=num 最左的位置
    public static int leftFindMost(int[] array,int num){
        if(array == null || array.length == 0){
            return -1;
        }
        //定义一个”左指针“
        int left = 0;
        //定义一个”右指针“
        int right = array.length - 1;
        //定义一个变量用来存储最左边的位置
        int ans = -1;
        //当left <= right 的时候进行二分查找
        while (left <= right){
            //定义一个中间位置
            int mid = (left + right) / 2;
            //当array[mid]>=num的时候就在mid的左边继续二分查找看是否还有>=num的数组元素并更新ans的值
            if(array[mid] >= num){
                ans = mid;
                right = mid - 1;
            }else if (array[mid] < num) {
                //如果array[mid]的值<num就在mid的右边继续查找
                left = mid + 1;
            }
        }
        //最后返回ans如果返回的是-1就说明在这个数组中没有>=num的数组元素
        return ans;
    }

非常规二分查找：在数组中找到<=num最右边的位置

代码：

//2.1二分查找的变形
    //在数组中找到<=num 最右边的位置
    public static int rightFindMost(int[] array, int num) {
        //定义一个”左指针“
        int left = 0;
        //定义一个”右指针“
        int right = array.length - 1;
        //定义一个变量用来存储最右边的位置
        int ans = -1;
        //当left < right 的时候就进行查找
        while (left <= right) {
            //定义一个中间位置的变量
            int mid = (left + right) / 2;
            if (array[mid] <= num) {
                //当找到一个数组元素>=num的时候就更新ans的值并在mid的右边继续进行查找
                ans = mid;
                left = mid + 1;
            }else{
                right = mid - 1;
            }
        }
        //最后返回ans如果最后返回的是-1就说明在这个数组中没有找到这样的数组元素
        return ans;
    }