【算法04】二分法常见题型

|
|
算法
字数统计：6,421 |
阅读时长：16分
部依
文章
18
标签
12
评论
1

1、在有序数组当中找到num

问题：在有序数组当中找到num（二分查找）

思路：

  1. 找到 0 和最后一个数的中位数， 将中位数和 我们的目标相比，

    1. 如果中位数小于目标，则将中位数定为左边界 继续向右二分查找。
    2. 如果中位数大于目标，则将中位数定为右边界 继续向左二分查找。
    3. 如果相等说明存在该值

  3. 如果我们的两个边界中间已经没有值了，或者左边界＞右边界了。则停止查找说明不存在该数值

答案：

public static boolean exist(int[] arr, int num) {
    if (arr == null || arr.length == 0) {
        return false;
    }
    int L = 0;
    int R = arr.length - 1;
    while (L <= R) {
        int mid = (L + R) / 2;
        if (arr[mid] == num) {
            return true;
        } else if (arr[mid] < num) {
            L = mid + 1;
        } else {
            R = mid - 1;
        }
    }
    return false;
}

暴力方法 ：

public static boolean exist_b(int[] arr, int num) {
    for (int i : arr) {
        if (i == num) {
            return true;
        }
    }
    return false;
}

测试方法 ：

/**
 * 生成一个长度为 0-maxLength 的 int 数组，范围是 [minValue,maxValue)<br/>
 * 只有正数 无负数<br/><br/>
 * <p>
 * 用法：<br/>
 * int[] array = ArrayTools.randomArray(20, 5, 10);<br/>
 * for (int i : array) {<br/>
 * &nbsp;&nbsp;&nbsp;&nbsp;System.out.print(i + " ");<br/>
 * }<br/>
 * 结果如下：<br/>
 * 8 7 7 8 9 7 5 5 9 9 6 5 8 8 7 6 9 7 8 5<br/>
 *
 * @param maxLength 数组长度
 * @param minValue  生成的数值都大于等于  minValue
 * @param maxValue  生成的数值都小于  maxValue
 * @return 生成一个长度为 0-maxLength 的 int 数组,范围是 [minValue,maxValue)
 * @throws IndexOutOfBoundsException 左边界不能大于右边界
 */
public static int[] randomArray(int maxLength, int minValue, int maxValue) {
    int[] array = new int[random(0, maxLength + 1)];
    if (minValue > maxValue) {
        throw new IndexOutOfBoundsException("左边界不能大于右边界");
    }
    int range = maxValue - minValue;
    for (int i = 0; i < array.length; i++) {
        array[i] = (int) (Math.random() * range) + minValue;
    }
    return array;
}

public static int[] randomArray(int maxLength, int maxValue) {
    return randomArray(maxLength, 0, maxValue);
}

public static void printArray(int[] array) {
    for (int i : array) {
        System.out.print(i + ",");
    }
    System.out.println();

}
public static void main(String[] args) {
    int testTimes = 100000;
    int maxLength = 500;
    int maxValue = 1000;
    int[] arr;
    int target;
    for (int i = 0; i < testTimes; i++) {
        arr = randomArray(maxLength, maxValue);
        Arrays.sort(arr);
        target = random(0, maxValue);
        if (exist(arr, target) != exist_b(arr, target)) {
            printArray(arr);
            System.out.println(target);
            System.out.println("判断出错");
            System.out.println("exist(arr, target) = " + exist(arr, target));
            System.out.println("exist_b(arr, target) = " + exist_b(arr, target));
            break;
        }
    }
    System.out.println("鉴定完成");
}

2、有序数组中找到 >=num 最左的位置

问题 : 有序数组中找到 >=num 最左的位置

思路：

  1. 在二分查找的基础上把符合条件的值的下标记录下来
  2. 然后继续二分查找，如果还是符合条件，并且新的下标小于原来的下标则更新下标
  3. 一直到循环不符合条件为止，如果有符合条件的则返回下标，如果不存在则返回-1

答案：

public static int mostLeftMoreNum(int[] arr, int num) {
    if (arr == null || arr.length == 0) {
        return -1;
    }
    int L = 0;
    int R = arr.length - 1;
    int index = -1;
    while (L <= R) {
        int mid = (L + R) / 2;
        if (arr[mid] >= num) {
            index = mid;
            R = mid - 1;
        } else {
            L = mid + 1;
        }
    }
    return index;
}

public static int test(int[] arr, int num) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] >= num) {
            return i;
        }
    }
    return -1;
}

public static void main(String[] args) {
    int testTimes = 500000;
    int maxLength = 50;
    int maxValue = 100;
    boolean success = true;
    for (int i = 0; i < testTimes; i++) {
        int[] arr = randomArray(maxLength, maxValue);
        Arrays.sort(arr);
        int target = random(0, maxValue);
        if (mostLeftMoreNum(arr, target) != test(arr, target)) {
            success = false;
            printArray(arr);
            System.out.println(target);
            System.out.println("判断出错");
            System.out.println("mostLeftMoreNum(arr, target) = " + mostLeftMoreNum(arr, target));
            System.out.println("test(arr, target) = " + test(arr, target));
            break;
        }
    }
    System.out.println(success ? "LUCK" : "Fucking fucked");
}

3、有序数组中找到 <=num 最右的位置

问题：有序数组中找到 <=num 最右的位置

思路：

  1. 跟上边最左边界类似，只不过是需要在 左边界更新的时候更新索引值
  2. 测试函数倒着便利数组一旦符合立即返回索引

答案：

public static int mostLeftMoreNum(int[] arr, int num) {
    if (arr == null || arr.length == 0) {
        return -1;
    }
    int L = 0;
    int R = arr.length - 1;
    int index = -1;
    while (L <= R) {
        int mid = (L + R) / 2;
        if (arr[mid] > num) {
            R = mid - 1;
        } else {
            index = mid;
            //这里不一样了！！！！ 
            L = mid + 1;
        }
    }
    return index;
}

public static int test(int[] arr, int num) {
    //遍历的顺序反了！！！！
    for (int i = arr.length - 1; i >= 0; i--) {
        //条件从大于等于 变成 小于等于
        if (arr[i] <= num) {
            return i;
        }
    }
    return -1;
}

public static void main(String[] args) {
    int testTimes = 500000;
    int maxLength = 50;
    int maxValue = 100;
    boolean success = true;
    for (int i = 0; i < testTimes; i++) {
        int[] arr = randomArray(maxLength, maxValue);
        Arrays.sort(arr);
        int target = random(0, maxValue);
        if (mostLeftMoreNum(arr, target) != test(arr, target)) {
            success = false;
            printArray(arr);
            System.out.println(target);
            System.out.println("判断出错");
            System.out.println("mostLeftMoreNum(arr, target) = " + mostLeftMoreNum(arr, target));
            System.out.println("test(arr, target) = " + test(arr, target));
            break;
        }
    }
    System.out.println(success ? "LUCK" : "Fucking fucked");
}

4、局部最小值问题

问题: 局部最小值问题

有一个数组，相邻两个数不想等，并且无序，如果一个数小于他左边的数也小与他右边的数，则称这个数为局部最小值，如果是边界的情况下只需要考虑有值的一边即可。（能否用二分法进行处理）

思路：

  1. 如果说 最左边的值或者最右边的值是局部最小值就可以直接返回了

  2. 如果说两者都不是局部最小值，那么 arr[1] 必然小于arr[0] ，从左边看越往后越小成下降趋势

  3. 同理 最右边的数 arr[n-2] < arr[n-1] 从右向左也是下降趋势， 那么0 和 n-1之间比存在 局部最小值

  4. 检查中点位置是不是局部最小值，如果是则返回。

  5. 如果 mid位置的数不是局部最小值

    1. arr[mid -1] < arr[mid] 在 [0,mid) 中间必存在局部最小值
    2. arr[mid] > arr[mid + 1]在 [mid,n-1) 中间必存在局部最小值

  7. 如果 L和 R 之间只有 L 和 R 两个值则跳出循环

    1. 比较L是否小于 R 。小于则返回 L，否则返回R

  9. 重复上述 （4-6）操作

答案：

public class Code03_BSAwesome {
    /**
     * 生成随机数组，且相邻数不相等
     *
     * @param maxLength 最大长度
     * @param maxValue  最大值
     * @return 随机数组
     */
    public static int[] randomArray(int maxLength, int maxValue) {
        int len = (int) (Math.random() * maxLength);
        int[] arr = new int[len];
        if (arr.length == 0) {
            return arr;
        }
        arr[0] = (int) (Math.random() * maxValue);
        for (int i = 1; i < arr.length; i++) {
            do {
                arr[i] = (int) (Math.random() * maxValue);
            } while (arr[i] == arr[i - 1]);
        }
        return arr;
    }

    public static void printArray(int[] array) {
        for (int i : array) {
            System.out.print(i + ",");
        }
        System.out.println();

    }
    //   arr 整体无序
    //   arr 相邻的数不想等
    public static int oneMinIndex(int[] arr) {
        if (arr == null || arr.length == 0) {
            return -1;
        }
        int N = arr.length;
        if (arr.length == 1) {
            return 0;
        }
        if (arr[0] < arr[1]) {
            return 0;
        }
        if (arr[N - 1] < arr[N - 2]) {
            return N - 1;
        }
        int L = 0;
        int R = N - 1;
        while (L < R - 1) {
            int mid = (L + R) / 2;
            if (arr[mid] < arr[mid - 1] && arr[mid] < arr[mid + 1]) {
                return mid;
            } else if (arr[mid] > arr[mid - 1]) {
                R = mid - 1;
            } else {
                L = mid + 1;
            }
        }
        return arr[L] < arr[R] ? L : R;
    }

    public static boolean test(int[] arr, int minIndex) {
        if (arr.length == 0) {
            return minIndex == -1;
        }
        int left = minIndex - 1;
        int right = minIndex + 1;
        boolean leftBoolean = left < 0 || arr[left] > arr[minIndex];
        boolean rightBoolean = right >= arr.length || arr[right] > arr[minIndex];
        return leftBoolean && rightBoolean;
    }

    public static void main(String[] args) {
        int testTimes = 500000;
        int maxLength = 50;
        int maxValue = 100;
        boolean success = true;
        for (int i = 0; i < testTimes; i++) {
            int[] arr = randomArray(maxLength, maxValue);
            int minIndex = oneMinIndex(arr);
            if (!test(arr, minIndex)) {
                success = false;
                printArray(arr);
                System.out.println("判断出错");
                System.out.println("目标函数minIndex结果 = " + minIndex);
                System.out.println("目标函数value结果 = " + arr[minIndex]);
                System.out.println("测试函数结果 = " + test(arr, minIndex));
                break;
            }
        }
        System.out.println(success ? "LUCK" : "Fucking fucked");
    }
}
文章作者: 部依
文章连结: /archives/bisectionmmethod
版权声明: 本部落格所有文章除特别声明外，均採用 CC BY-NC-SA 4.0 许可协议。转载请註明来自 部依！
上一篇 下一篇