好玩的网站列表

二分查找是一种针对于有序数据集合的查找算法，也叫折半查找算法。类似分治的思想，每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为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