Java基础数据结构 1.4 改进的二分查找法（平衡）

[zemise]

1.4 改进的二分查找法（平衡）

分析if的判断次数

未改进的算法：如果要查找的元素在左边就要判断L次，若在右边就要判断2*L次。

public class BinarySearch {

    /**
     * <p>
     * 未改进的二分查找基础版
     * <p>
     *
     * @param a      待查找的升序数组
     * @param target 待查询的目标值
     * @return int 找到返回索引，找不到返回 -1
     * @author Zemise
     * @since 2023/06/12
     */
    public static int binarySearchBasic(int[] a, int target) {
        int i = 0;
        int j = a.length - 1;           // 设置指针和初始值
      
       // L次 元素在最左边L次		元素在最右边 if的比较次数则为 2*L 次
        while (i <= j) {                // i～j 范围内还有东西
          
            int m = (i + j) >>> 1;

            if (target < a[m]) {        // 目标在左边
                j = m - 1;
            } else if (a[m] < target) { // 目标在右边
                i = m + 1;
            } else {                    // 找到了
                return m;
            }
        }

        return -1;
    }

改进版

public static int binarySearch(int[] a, int target){
    int i = 0;           //1 在左闭右开的区间，i指向的可能是目标 j只作为边界
    int j = a.length;
    while(1 < j - i){    //2 不在循环内找出，等范围内只剩i时，退出循环，在循环外比较a[i]与target
        int m = (i+j) >>> 1; 
        if(target < a[m]){
            j = m;
        }
        else{
            i = m;
        }
    }
  
    if(a[i] == target){    //3 在循环外比较平均次数减少了
        return i;          //4 时间复杂度Ɵ(log(n))
    }
    else{
        return -1;
    }
}

改进之后:

​ 优点：循环内的平均比较次数减少了

​ 缺点：为改进之前最好的情况时间复杂度为$O(1)$

​ 改动之后最好和最坏的情况都是$O(log(n))$

@Test
@DisplayName("binarySearchBasic java自带版")
public void test8() {
  int[] a = {2, 5, 8};
  int target = 4;

  /*
            [2, 5, 8]       a
            [2, 0, 0, 0]    b
            [2, 4, 0, 0]    b
            [2, 4, 5, 8]    b
         */

  // 注意，下方说的插入点，其实就是在数组中没有找到目标数据时，会返回目标数据该插入的索引位置
  int i = Arrays.binarySearch(a, target);
  // -2 = -插入点 - 1
  // -2 + 1 = -插入点

  if (i < 0) {
    int insertIndex = Math.abs(i + 1); // 获得插入点索引

    int[] b = new int[a.length + 1];
    System.arraycopy(a, 0, b, 0, insertIndex);
    b[insertIndex] = target;

    System.arraycopy(a, insertIndex, b, insertIndex + 1, a.length - insertIndex);
    System.out.println(Arrays.toString(b));
  }
}