数据结构与算法(12)-二分查找

  1. 1. 二分查找的基本实现
  2. 2. 二分查找的应用场景局限性
  3. 3. 二分查找的实际应用与变体
    1. 3.1 查找第一个值等于给定值的元素

二分查找是一种针对于有序数据集合的查找算法,也叫折半查找算法。类似分治的思想,每次都通过跟区间的中间元素对比,将待查找的区间缩小为之前的一半,直到找到要查找的元素,或者区间被缩小为0. 查找速度为O(logn)

思考题:1000万个整数数据,每个数据8字节,

1. 二分查找的基本实现

public int bsearch(int[] a, int n, int value) {
// 定基准点
  int low = 0;
  int high = n - 1;

// 停止条件
  while (low <= high) {
    // 定二分点
    int mid = (low + high) / 2;
    if (a[mid] == value) {
      return mid;
    } else if (a[mid] < value) {
     // 保证是活循环.. 
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }

  return -1;
}



// 二分查找的递归实现
public int bsearch(int[] a, int n, int val) {
  return bsearchInternally(a, 0, n - 1, val);
}

private int bsearchInternally(int[] a, int low, int high, int value) {
  if (low > high) return -1;

  int mid =  low + ((high - low) >> 1);
  if (a[mid] == value) {
    return mid;
  } else if (a[mid] < value) {
    return bsearchInternally(a, mid+1, high, value);
  } else {
    return bsearchInternally(a, low, mid-1, value);
  }
}
  • 循环退出条件
    • low <= high
  • mid取值
    • mid = low + (high - low)/2
    • 因为如果值太大的话,会溢出的
  • low high的更新
    • low = mid + 1
    • high = mid - 1

2. 二分查找的应用场景局限性

  • 二分查找以来的是顺序表结构 – 数组
    • 因为二分查找需要按照下标来随机访问元素
  • 针对的是有序数据 – 静态数据集
    • 更适用在插入,删除不频繁,一次排序多次查找的场景当中
    • 针对动态变化的数据集合,二分查找就不再适用了
  • 数据量太小不需要适用二分查找
  • 如果数据之间的比较非常耗时,我们需要尽力减少比较的次数,那么二分查找就是很好的方式了

3. 二分查找的实际应用与变体

3.1 查找第一个值等于给定值的元素

public int bsearch(int[] a, int n, int value) {
  int low = 0;
  int high = n - 1;
  while (low <= high) {
    int mid =  low + ((high - low) >> 1);
    if (a[mid] > value) {
      high = mid - 1;
    } else if (a[mid] < value) {
      low = mid + 1;
    } else {
      // 注意这里的判断,中止条件时mid为0 或者左一个的值和现在的值不相等 
      if ((mid == 0) || (a[mid - 1] != value)) return mid;
      else high = mid - 1;
    }
  }
  return -1;
}
  • 写二分相关的算法要注意的点有
    • 终止条件
    • 区间上下界的更新方法
    • 返回值的选择

转载请注明来源,欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 stone2paul@gmail.com

文章标题:数据结构与算法(12)-二分查找

文章字数:613

本文作者:Leilei Chen

发布时间:2020-02-09, 10:07:07

最后更新:2020-02-09, 10:07:27

原始链接:https://www.llchen60.com/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95-12-%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE/

版权声明: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

目录
×

喜欢就点赞,疼爱就打赏