二分法 记住有效条件 L <= R 才是循环的有效条件 

    1.     // arr保证有序
    2.     public static boolean find(int[] arr, int num) {
    3.         if (arr == null || arr.length == 0) {
    4.             return false;
    5.         }
    6.         int L = 0;
    7.         int R = arr.length - 1;
    8.         while (L <= R) {
    9.             int mid = (L + R) / 2;
    10.             if (arr[mid] == num) {
    11.                 return true;
    12.             } else if (arr[mid] < num) {
    13.                 L = mid + 1;
    14.             } else {
    15.                 R = mid - 1;
    16.             }
    17.         }
    18.         return false;
    19.     }

    在有序数组中找到>=num最左的位置
    1位置 就是>=2的最左位置
    image.png
    在数组中点位置 5 找到>=2 的位置 变量t记录先记录位置 数组有序 舍弃掉记录的右半部
    指针左移 0-4范围 中点 2位置 不是>=2的 变量t不更新
    3-4 范围 找 中点位置3 是>=2 的 变量t更新 3位置左边可能也有但是已经没数了
    image.png

    1.     // arr有序的，>=num 最左
    2.     public static int mostLeftNoLessNumIndex(int[] arr, int num) {
    3.         if (arr == null || arr.length == 0) {
    4.             return -1;
    5.         }
    6.         int L = 0;
    7.         int R = arr.length - 1;
    8.         int ans = -1;
    9.         while (L <= R) {
    10.             int mid = (L + R) / 2;
    11.             if (arr[mid] >= num) {
    12.                 ans = mid;
    13.                 R = mid - 1;
    14.             } else {
    15.                 L = mid + 1;
    16.             }
    17.         }
    18.         return ans;
    19.     }

    局部最小值
    有一个无序数组 任意相邻的两个数不相等
    image.png
    确定边界值 0位置和1位置 n-2位置和n-1位置 谁小返回谁 。 中点mid也是 如果最小就直接返回
    mid比左边大 砍掉右边 左边继续二分
    注意边界条件 mid-1 mid+1 都要在 L-R范围

    1. // arr 相邻的数不相等！
    2.     public static int oneMinIndex(int[] arr) {
    3.         if (arr == null || arr.length == 0) {
    4.             return -1;
    5.         }
    6.         int N = arr.length;
    7.         if (N == 1) {
    8.             return 0;
    9.         }
    10.         if (arr[0] < arr[1]) {
    11.             return 0;
    12.         }
    13.         if (arr[N - 1] < arr[N - 2]) {
    14.             return N - 1;
    15.         }
    16.         int L = 0;
    17.         int R = N - 1;
    18.         // L...R 肯定有局部最小
    19.         while (L < R - 1) {
    20.             int mid = (L + R) / 2;
    21.             if (arr[mid] < arr[mid - 1] && arr[mid] < arr[mid + 1]) {
    22.                 return mid;
    23.             } else {
    24.                 if (arr[mid] > arr[mid - 1]) {
    25.                     R = mid - 1;
    26.                 } else {
    27.                     L = mid + 1;
    28.                 }
    29.             }
    30.         }
    31.         return arr[L] < arr[R] ? L : R;
    32.     }
    34.     // 生成随机数组，且相邻数不相等
    35.     public static int[] randomArray(int maxLen, int maxValue) {
    36.         int len = (int) (Math.random() * maxLen);
    37.         int[] arr = new int[len];
    38.         if (len > 0) {
    39.             arr[0] = (int) (Math.random() * maxValue);
    40.             for (int i = 1; i < len; i++) {
    41.                 do {
    42.                     arr[i] = (int) (Math.random() * maxValue);
    43.                 } while (arr[i] == arr[i - 1]);
    44.             }
    45.         }
    46.         return arr;
    47.     }

    对数器

    1.     // 也用于测试
    2.     public static boolean check(int[] arr, int minIndex) {
    3.         if (arr.length == 0) {
    4.             return minIndex == -1;
    5.         }
    6.         int left = minIndex - 1;
    7.         int right = minIndex + 1;
    8.         boolean leftBigger = left >= 0 ? arr[left] > arr[minIndex] : true;
    9.         boolean rightBigger = right < arr.length ? arr[right] > arr[minIndex] : true;
    10.         return leftBigger && rightBigger;
    11.     }
    13.     public static void printArray(int[] arr) {
    14.         for (int num : arr) {
    15.             System.out.print(num + " ");
    16.         }
    17.         System.out.println();
    18.     }
    20.     public static void main(String[] args) {
    21.         int maxLen = 100;
    22.         int maxValue = 200;
    23.         int testTime = 1000000;
    24.         System.out.println("测试开始");
    25.         for (int i = 0; i < testTime; i++) {
    26.             int[] arr = randomArray(maxLen, maxValue);
    27.             int ans = oneMinIndex(arr);
    28.             if (!check(arr, ans)) {
    29.                 printArray(arr);
    30.                 System.out.println(ans);
    31.                 break;
    32.             }
    33.         }
    34.         System.out.println("测试结束");
    36.     }

    时间复杂度
    image.png
    要假设最差情况

    复杂度排序表
    image.png

    动态数组
    arrayList就是动态数组 会自动扩容
    问题 扩容行为 会不会影响 arrayList的整体表现

    看放入N个数 扩容的总代价
    扩容代价 将原数组内容 放入新数组
    代价 规律为等比数列 等比数列最后的总代价为 O(N)
    加N为O(N) 加1可化为 O(1)
    动态数组 虽然存在扩容行为 但是在时间复杂度上没有影响 可以做到和固定数组一样 还支持动态扩容（仅只时间复杂度）

    image.png
    哈希表不论存多少数据 增删改差 都是常数时间O(1) 只是比较大的常数时间 比数组寻址的时间要大
    不会去查test1的引用地址 而是直接查内容
    image.png
    哈希表 值查的是一个东西 就存在 按值传递
    自定义的非基础类型 非原生类型 按引用传递 只关心内存地址

    有序表 treemap 增删改差 时间复杂度 logN级别
    image.png