已知一个有序数组arr，和一个数字num。返回数组中是否含有这个数字。(使用二分法)

package class01;

import java.util.Arrays;

/**
 * 二分法
 * 已知一个有序数组arr，和一个数字num。返回数组中是否含有这个数字。(使用二分法)
 * <p>
 * 常规二分法的时间复杂度，O(logN)。
 * O(log2N)，即log以2为底，N的对数。
 * <p>
 * 一次砍一半，一次砍一半，一次砍一半。
 * N个数，一共砍几次呢？一共砍了O(log2N)次，每砍一次，看一眼这个中点上的数，是O(1)的。
 * 所以就是log2N乘以1，还是O(log2N)。
 */
public class Code04_BSExist {
    public static void main(String[] args) {
        //当写while (L < R)时，是错误的，反例如下。正确的写法是while (L <= R)。
        //-24 -21 -19 -13 -10 -8 0 7 10 10 20
        //int[] arr = {-24, -21, -19, -13, -10, -8, 0, 7, 10, 10, 20};
        int maxSize = 30;
        int maxValue = 30;
        int testTimes = 10;
        int num = 7;
        boolean flag = true;
        for (int i = 0; i < testTimes; i++) {
            int[] arr = generateRandomArray(maxSize, maxValue);
            Arrays.sort(arr);
            printArr(arr);
            System.out.println(num);
            boolean b = exist(arr, num);
            System.out.println(b);
            System.out.println("---");
            boolean test = test(arr, num);
            if (b != test) {
                flag = false;
                break;
            }
        }
        System.out.println(flag ? "nice!" : "oops!");
    }


    public static boolean exist(int[] sortedArr, int num) {
        int L = 0;
        int R = sortedArr.length - 1;
        while (L <= R) {
            int mid = L + ((R - L) >> 1);//必须要加括号，否则会先算加法，导致死循环。
            if (sortedArr[mid] < num) {
                L = mid + 1;
            } else if (sortedArr[mid] > num) {
                R = mid - 1;
            } else {
                return true;
            }
        }
        return false;
    }

    public static int[] generateRandomArray(int maxSize, int maxValue) {
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
        }
        return arr;
    }

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

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

}