02.二分查找元素

二分查找

• 1.基本思想
• 2.排序过程
• 3.代码实现
• 4.如何优化
• 5.复杂度
• 6.使用场景

1.基本思想

• 有序的序列，每次都是以序列的中间位置的数来与待查找的关键字进行比较，每次缩小一半的查找范围，直到匹配成功。
• 注意如果是无需数组，则首先要排序成有序数组，二分查找只能对有序序列。

2.排序过程

• ① 首先确定整个查找区间的中间位置 mid = （ left + right ）/ 2
• ② 用待查关键字值与中间位置的关键字值进行比较；
  • 若相等，则查找成功
  • 若大于，则在后（右）半个区域继续进行折半查找
  • 若小于，则在前（左）半个区域继续进行折半查找
• ③ 对确定的缩小区域再按折半公式，重复上述步骤。
  • 最后，得到结果：要么查找成功， 要么查找失败。

3.代码实现

• 代码如下所示

  // 二分查找递归实现
  public static int binSearch(int srcArray[], int start, int end, int key) {
      int mid = (end - start) / 2 + start;
      if (srcArray[mid] == key) {
          return mid;
      }
      if (start >= end) {
          return -1;
      } else if (key > srcArray[mid]) {
          //key 大于中间值，那么就从右边查找
          return binSearch(srcArray, mid + 1, end, key);
      } else if (key < srcArray[mid]) {
          //key 小于中间值，那么就从左边查找
          return binSearch(srcArray, start, mid - 1, key);
      }
      return -1;
  }
  
  // 二分查找普通循环实现
  public static int binSearch(int srcArray[], int key) {
      int mid = srcArray.length / 2;
      if (key == srcArray[mid]) {
          return mid;
      }
  
      int start = 0;
      int end = srcArray.length - 1;
      while (start <= end) {
          mid = (end - start) / 2 + start;
          if (key < srcArray[mid]) {
              end = mid - 1;
          } else if (key > srcArray[mid]) {
              start = mid + 1;
          } else {
              return mid;
          }
      }
      return -1;
  }

4.如何优化

• 优点：每经过一次比较,查找范围就缩小一半。经log2n次计较就可以完成查找过程。
• 缺点：因要求有序，所以要求查找数列必须有序，而对所有数据元素按大小排序是非常费时的操作。另外，顺序存储结构的插入、删除操作不便利。

5.复杂度

• 时间复杂度
  • 采用的是分治策略
  • 最坏的情况下两种方式时间复杂度一样：O(log2 N)
  • 最好情况下为O（1）
• 空间复杂度
  • 算法的空间复杂度并不是计算实际占用的空间，而是计算整个算法的辅助空间单元的个数
  • 非递归方式：
    • 由于辅助空间是常数级别的所以：空间复杂度是O(1);
  • 递归方式：
    • 递归的次数和深度都是log2 N,每次所需要的辅助空间都是常数级别的：空间复杂度：O(log2N )

6.使用场景

• 优缺点分析
  • 当查找表不会频繁有更新、删除操作时，使用折半查找是比较理想的。如果查找表有较频繁的更新、删除操作，维护表的有序会花费比较大的精力，不建议使用该查找方式。