二分查找

文章目录

1. 1. 一、最常见写法
2. 2. 二、相同值找坐标最小的
3. 3. 三、相同值找坐标最大的

一、最常见写法

• 注意while条件
• 注意if/else中条件判断

  public static int binarySearch(int[] array, int n, int value) {
      int start = 0;
      int end = n - 1;
      int middle;
      while (start <= end) {
          middle = start + (end - start) / 2;
          if (array[middle] > value) {
              end = middle - 1;
          }
          if (array[middle] < value) {
              start = middle + 1;
          }
          if (array[middle] == value) return middle;
      }
      return start;
  }

二、相同值找坐标最小的

• start < end
• start = middle

  public static int binarySearch_left(int[] array, int n, int value) {
      int start = 0;
      int end = n - 1;
      int middle;
      while (start <= end) {
          middle = start + (end - start) / 2;
          if (array[middle] >= value) {
              end = middle - 1;
          }
          if (array[middle] < value) {
              start = middle + 1;
          }
      }
      return start;
  }

三、相同值找坐标最大的

• start < end
• end = middle

  public static int binarySearch_right(int[] array, int n, int value) {
      int start = 0;
      int end = n - 1;
      int middle;
      while (start <= end) {
          middle = start + (end - start) / 2;
          if (array[middle] > value) {
              end = middle - 1;
          }
          if (array[middle] <= value) {
              start = middle + 1;
          }
      }
      return start;
  }