笔记: 数据结构与算法--时间复杂度二分查找数组

算法复杂度

• 不依赖于环境因素
• 事前分析法
  • 计算最坏情况的时间复杂度
  • 每一条语句的执行时间都按照t来计算

时间复杂度

• 大O表示法
  • n = 数据量 ; f(n) = 实际的执行条数
  • 当存在一个n₀ , 使得 n > n₀,并且 c * g(n) 恒> f(n) : 渐进上界(算法最坏的情况)
  • 那么f(n)的时间复杂度 => O(g(n))
• 大O表示法
  • f(n)中的常数量省略
  • f(n)中较低次幂省略
  • log₂(n) => log(n)
• 常见的表示
  • O(1) > O(log(n)) >> O(n) > O(nlog(n)) >> O(n²) > O(2^n) >> O(n!)

空间复杂度

• 除原始参数以外,额外空间成本

二分查找

基础版

1. 步骤

   1. 有序数组A , 目标值target
   2. 左右索引值 : i = 0 , j = n - 1;
   3. 判断 i > j => 结束查找,没找到
   4. 中间索引 m = ( i + j) / 2 : 整形自动向下取整
   5. 判断 m > target : j = m -1; -> 跳到第三步继续执行
   6. 判断 m < target : i = m + 1; -> 跳到第三步继续执行
   7. 判断 m = target : 得到结果结束程序,返回索引值

2. 代码如下

   /*** 编写二分查找方法* @param A : 有序数组a* @param target : 目标查找值* @return 返回索引值*/public static int binarySearchBasic(int[] A, int target) {// 定义左右指针int i = 0, j = A.length - 1;// 定义循环条件while (i <= j) {// 定义中间指针m// int m = (i + j) / 2; int m = (i + j) >>> 1; // 判断A[m] 值 与 target值if (target < A[m]){// 中间值大 : 指针[m , j]中的值都会比target值大j = m - 1;} else if (A[m] < target){// 中间值小 : 指针[i , m]中的值都会比target值小i = m + 1;} else {// A[m] == target: 得到结果,结束循环,返回mreturn m;}}//i > j : 结束循环return -1; // 结束循环,返回-1}
   

3. 问题一 : 代码while循环中为什么是i <= j , 而不是 i < j ?

   答 : 首先 代码return -1; 本身表示的就是在 i>j 的情况下结束,没有找到,返回-1; , 那么相反对应的循环内就应该为 i <= j

   其次, while(i < j ) 表示的是 只有i,j中间的m会参与比较 ; 而while(i <= j) : 表示 i , j所指向的元素 也会参与比较. 当i == j 的时候, m = i = j = (i + j) /2

4. 问题二: 代码 int m = (i + j) / 2; 是否有问题?

   答: 有问题.

   ​ 假设 j 的值为整数类型最大值 (Integer.MAX_VALUE - 1) , 并且target值在数组的右侧 (target > A[m]) , 那么我们就需要将 索引i 的值调到m的右侧

   ​ 即 : i = (i + j) /2 + 1; j = 整数类型最大值 = Integer.MAX_VALUE - 1;

   ​ 那么根据Java int类型的特性, Java二进制首位为符号位,则会导致下一次进行 m = (i + j) / 2 的时候,使m成为负数

   解决办法: 无符号右移运算符 数字 >>> 位数n

   ​ 在二进制中,二进制码整体向右平移指定位数n就相当于n / 2ⁿ , 数字 >>> 1 => 数字 / 2运算取整

改动版

1. 步骤

   1. 让右指针作为边界,必须不参与比较运算
   2. 循环不能有i=j的情况,如果i=j的话,则会造成m = i = j = (i + j) / 2 , 则不符合第一点j不参与比较运算的条件
   3. 当m指针所对应的值 > target值时,让j指针=m , 因为m指针对应的值已经参与过比较,并且肯定不等于target值,可作为边界不参与比较运算.
      1. 如果还是j = m - 1情况, m - 1的指针存在这等于target的可能,于第一点让j作为边界条件不服.
      2. 并且,当j= m - 1 , 如果要查找的target值不在数组A中时,会出现死循环的情况

2. 代码如下

       public static int binarySearchAlter(int[] A, int target) {// 改动一: 其中右指针j作为边界, 必须不参与运算比较int i = 0, j = A.length;// 定义循环条件 , 改动二: 由于不让j指针值参与比较, 故不需要i=j的情况,当i=j时,j被带着参与了比较,当target值不是数组值的时候,会导致死循环的情况while (i < j) {int m = (i + j) >>> 1;if (target < A[m]) {// 改动三: j作为边界,不参与比较.故当判断出来target值在m指针左侧时,m指针对应值已经判断过了,不可能和target相等,让j=m,及让j作为一个不可能相等的边界使用j = m;} else if (A[m] < target) {i = m + 1;} else {return m;}}return -1;}
   

平衡版

1. 代码如下

   /*** 二分查找平衡版** @param A      : 有序数组a* @param target : 目标查找值* @return 返回索引值*/public static int binarySearchBalance(int[] A, int target) {// 定义左右边界,左边i指针对应的值可能target , 右指针j作为边界, 必须不参与运算比较int i = 0, j = A.length;// 定义循环条件 , 目的为缩小比较范围,将最后比较功能放到循环以外// 由i < j => 0 < j - i 改为 1 < j - i; 表示[i , j]区间内待比较的个数是否有1个以上while (1 < j - i) {// 定义中间索引int m = (i + j) >>> 1;if (target < A[m]) {// j作为右边界,不参与比较.故当判断出来target值在m指针左侧时,m指针对应值已经判断过了,不可能和target相等,让j=m,及让j作为一个不可能相等的边界使用j = m;} else {// 及 A[m] <= target的情况,及 i指针对应的值是有可能为target结果的i = m;}}// 将缩减范围后剩余的一个索引i所对应的值与target进行比较if (A[i] == target){return i;} else {return -1;}}
   

二分查找-Java版源码

• 通过Arrays.binarySearch(int[] arr, int key);方法调用

    /*** Searches the specified array of ints for the specified value using the* binary search algorithm.  The array must be sorted (as* by the {@link #sort(int[])} method) prior to making this call.  If it* is not sorted, the results are undefined.  If the array contains* multiple elements with the specified value, there is no guarantee which* one will be found.** @param a the array to be searched* @param key the value to be searched for* @return index of the search key, if it is contained in the array;*         otherwise, <code>(-(<i>insertion point</i>) - 1)</code>.  The*         <i>insertion point</i> is defined as the point at which the*         key would be inserted into the array: the index of the first*         element greater than the key, or {@code a.length} if all*         elements in the array are less than the specified key.  Note*         that this guarantees that the return value will be &gt;= 0 if*         and only if the key is found.*/public static int binarySearch(int[] a, int key) {return binarySearch0(a, 0, a.length, key);}// Like public version, but without range checks.private static int binarySearch0(int[] a, int fromIndex, int toIndex,int key) {int low = fromIndex;int high = toIndex - 1;while (low <= high) {int mid = (low + high) >>> 1;int midVal = a[mid];if (midVal < key)low = mid + 1;else if (midVal > key)high = mid - 1;elsereturn mid; // key found}return -(low + 1);  // key not found.}

二分查找对于重复元素查找的处理

获取重复最左侧索引值

1. 步骤

   1. 添加一个结果变量索引值,用来存储当m索引值与target相等时,存储m索引值 ,
   2. 当相等时,j继续缩小边界,程序继续直到程序结束,获取最左侧结果
   3. i > j : 结束循环 , 返回结果索引值

2. 代码如下

   public static int binarySearchLeftMost(int[] A, int target) {// 定义左右指针int i = 0, j = A.length - 1;// 定义结果变量索引值int resIndex = -1;// 定义循环条件while (i <= j) {// 定义中间指针mint m = (i + j) / 2;// 判断A[m] 值 与 target值if (target < A[m]){// 中间值大 : 指针[m , j]中的值都会比target值大j = m - 1;} else if (A[m] < target){// 中间值小 : 指针[i , m]中的值都会比target值小i = m + 1;} else {// A[m] == target: 将结果存储到结果索引值中, 并将右侧边界缩小,继续进行程序,直到程序结束,获取最左侧结果resIndex = m;j = m - 1;}}//i > j : 结束循环 , 返回结果索引值return resIndex;}
   

3. 获取重复最右侧索引值 : 将上放代码第20行 j = m - 1; => 改为 i = m + 1; 即可

修改返回值意义

• 获取<= 索引值 最靠右的索引值结果 , 代码如下:

  	public static int binarySearchRightMost1(int[] A, int target) {// 定义左右指针int i = 0, j = A.length - 1;// 定义循环条件while (i <= j) {// 定义中间指针mint m = (i + j) / 2;// 判断A[m] 值 与 target值if (target < A[m]) {    j = m - 1;} else {i = m + 1;}}//返回  <= 索引值 最靠右的索引值结果return i - 1;}
  

• 获取 >= target 最靠左的索引位置 , 代码如下:

  	public static int binarySearchLeftMost1(int[] A, int target) {// 定义左右指针int i = 0, j = A.length - 1;// 定义循环条件while (i <= j) {// 定义中间指针mint m = (i + j) / 2;// 判断A[m] 值 与 target值if (target <= A[m]) {// 中间值>= targetj = m - 1;} else {// 中间值小 : 指针[i , m]中的值都会比target值小i = m + 1;}}//返回 >= target最靠左的索引位置return i;}
  

应用

• leftMost() :
  • 求排名 leftMost() + 1 ;
  • 求前任 leftMost() - 1 ;
• rightMost() :
  • 求后任 rightMost + 1;
• 最近邻居问题
  • 求前任 , 求后任
  • 计算两个值 离 本值 更小的
• 范围查询
  • x < n : [0 , leftMost(n) - 1]
  • x <= n : [0 , rightMost(n)]
  • x > n : [rightMost(n) + 1 , ∞]
  • x >= n : [leftMost(n) , ∞]
  • n <= x <= m : [leftMost(n) , rightMost(m)]
  • n < x < m : [rightMost(n) + 1 . leftMost(m) - 1]

性能

• 时间复杂度最坏情况 : O(log(n))
• 空间复杂度 : O(1)

数组

• 连续存储

  • -> 故可以通过索引值计算地址
  • 公式 : 索引位置 + i * 字节数

• 随机访问时间复杂度: O(1)

• 动态数组类需要三个东西

  • 数组容量
  • 数组逻辑大小 : 就是数组实际存了几个值
  • 静态数组

• 给数组添加元素

  • 在末尾添加元素 => 给数组size位置上添加元素 -> 即调用下面方法

  • 给数组指定位置添加元素

    • 将数组指定位置后的元素后移
    • 插入元素到指定位置上

  • 插入删除的时间复杂度: O(n)

  • 代码如下:

        // 给数组添加元素 => 给数组size位置上添加元素private void add(int element){
    //        arrs[size] = element;
    //        size++;addAppoint(size, element);}// 给数组指定位置添加元素private void addAppoint(int index , int element){if (index >= 0 && index < size){System.arraycopy(arrs, index, arrs, index + 1, size - index);}arrs[index] = element;size++;}
    

• 当数组存储元素达到容量上限,需要考虑数组扩容问题

  • 每次添加元素的时候,判断size和capacity

    • 定义一个新数组,容量大小是旧数组的1.5倍或两倍
    • 将旧数组的数据复制到新数组中
    • 将新数组的引用值 赋值 给旧数组

  • 使用懒惰初始化思想优化代码

  • 代码如下:

        private void checkArrsCapacity() {if (size == 0) {arrs = new int[capacity];} else if (capacity == size) {capacity += capacity >> 1; // 扩大数组容量int[] newArrs = new int[capacity];System.arraycopy(arrs, 0, newArrs, 0, size);arrs = newArrs;}}@Test@DisplayName("测试扩容")public void test5() {DynamicArray dynamicArray = new DynamicArray();for (int i = 0; i < 9; i++) {dynamicArray.add(i + 1);}assertIterableEquals(List.of(1, 2, 3, 4, 5, 6, 7, 8, 9), dynamicArray);}
    

• 给动态数组遍历的三种方式

  • 使用Consumer函数式接口,实现遍历

        // 动态数组的遍历 , 使用Comsumer函数式接口实现public void foreach(Consumer<Integer> consumer){for (int i = 0; i < size; i++) {consumer.accept(arrs[i]);}}@Testpublic void test3() {DynamicArray dynamicArray = new DynamicArray();dynamicArray.add(1);dynamicArray.add(2);dynamicArray.add(3);dynamicArray.foreach(System.out::println);}
    

  • 使用迭代器实现遍历

        @Overridepublic Iterator<Integer> iterator() {return new Iterator<Integer>() {int i = 0;@Overridepublic boolean hasNext() {return i < size;}@Overridepublic Integer next() {return arrs[i++];}};}@Testpublic void test2() {DynamicArray dynamicArray = new DynamicArray();dynamicArray.add(1);dynamicArray.add(2);dynamicArray.add(3);for (Integer element : dynamicArray) {System.out.println(element);}}
    

  • 使用stream流实现遍历

        // 动态数组的遍历: 使用stream流实现public IntStream stream(){return IntStream.of(Arrays.copyOfRange(arrs, 0, size));}@Testpublic void test1() {DynamicArray dynamicArray = new DynamicArray();dynamicArray.add(1);dynamicArray.add(2);dynamicArray.add(3);dynamicArray.stream().forEach(System.out::println);}
    

• 动态数组的删除

  • 使用system.arraycopy方法, 将要删除指针后的元素向前移动一位
  • 插入删除: O(n)

      public int remove(int index) {int removeNum = arrs[index]; // 返回删除数据if (index < size - 1) {System.arraycopy(arrs, index + 1, arrs, index, size - index - 1);}size--;return removeNum;}// 使用断言进行测试@Test@DisplayName("测试删除")public void test4() {DynamicArray dynamicArray = new DynamicArray();dynamicArray.add(1);dynamicArray.add(2);dynamicArray.add(3);dynamicArray.add(4);dynamicArray.add(5);int remove = dynamicArray.remove(3);
  //        System.out.println("remove = " + remove);assertEquals(4 , remove);// 遍历剩余数组元素// dynamicArray.foreach(System.out::println);assertIterableEquals(List.of(1,2,3,5), dynamicArray);}