二分法查找

算法
留言

二分查找针对的是一个有序的数据集合，查找思想有点类似分治思想。每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为 0。

O(logn) 惊人的查找速度

我们假设数据大小是 n，每次查找后数据都会缩小为原来的一半，也就是会除以 2。最坏情况下，直到查找区间被缩小为空，才停止。

可以看出来，这是一个等比数列。其中 n/2k=1 时，k 的值就是总共缩小的次数。而每一次缩小操作只涉及两个数据的大小比较，所以，经过了 k 次区间缩小操作，时间复杂度就是 O(k)。通过 n/2k=1，我们可以求得 k=log2n，所以时间复杂度就是 O(logn)。

二分查找是我们目前为止遇到的第一个时间复杂度为 O(logn) 的算法。后面章节我们还会讲堆、二叉树的操作等等，它们的时间复杂度也是 O(logn)。我这里就再深入地讲讲 O(logn) 这种对数时间复杂度。这是一种极其高效的时间复杂度，有的时候甚至比时间复杂度是常量级 O(1) 的算法还要高效

二分法查找容易出错的地方
循环退出条件、mid 的取值，low 和 high 的更新。

二分查找的递归与非递归实现

// 循环实现
// 数组必须有序 不存在重复
const binarySearch = (sortedArr, target) => {
  if (sortedArr.length === 0) return -1;
  let low = 0;
  let high = sortedArr.length - 1;
  while (low <= high) {
    const mid = Math.floor((low + high) / 2);
    if (target === sortedArr[mid]) {
      return mid;
    } else if (target < sortedArr[mid]) {
      high = mid - 1;
    } else {
      low = mid + 1;
    }
  }
  return -1;
};
// 递归实现
function binarySearch(a, n, val) {
  return binarySearchInternally(a, 0, n - 1, val);
}
function binarySearchInternally(a, low, high, value) {
  if (low > high) return -1;
  const mid = Math.floor((low + high) / 2);
  if (a[mid] == value) {
    return mid;
  } else if (a[mid] < value) {
    return binarySearchInternally(a, mid + 1, high, value);
  } else {
    return binarySearchInternally(a, low, mid - 1, value);
  }
}

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

首先，二分查找依赖的是顺序表结构，简单点说就是数组。
其次，二分查找针对的是有序数据。
再次，数据量太小不适合二分查找。
最后，数据量太大也不适合二分查找。

四种常见的二分查找变形问题

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

如果我们将这个问题稍微修改下，有序数据集合中存在重复的数据，我们希望找到第一个值等于给定值的数据

function binarySearch(a, n, value) {
  let low = 0;
  let high = n - 1;
  while (low <= high) {
    const mid = low + ((high - low) >> 1);
    if (a[mid] > value) {
      high = mid - 1;
    } else if (a[mid] < value) {
      low = mid + 1;
    } else {
      //如果 mid 等于 0，那这个元素已经是数组的第一个元素，那它肯定是我们要找的；
      // 如果 mid 不等于 0，但 a[mid]的前一个元素 a[mid-1]不等于 value，那也说明 a[mid]就是我们要找的第一个值等于给定值的元素。
      if (mid == 0 || a[mid - 1] != value) return mid;
      else high = mid - 1;
    }
  }
  return -1;
}

查找最后一个值等于给定值的元素

function binarySearch(a, n, value) {
  let low = 0;
  let high = n - 1;
  while (low <= high) {
    const mid = low + ((high - low) >> 1);
    if (a[mid] > value) {
      high = mid - 1;
    } else if (a[mid] < value) {
      low = mid + 1;
    } else {
      //如果 mid 等于 0，那这个元素已经是数组的第一个元素，那它肯定是我们要找的；
      // 如果 mid 不等于 0，但 a[mid]的前一个元素 a[mid-1]不等于 value，那也说明 a[mid]就是我们要找的第一个值等于给定值的元素。
      if (mid == n - 1 || a[mid + 1] != value) return mid;
      else low = mid - 1;
    }
  }
  return -1;
}

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

function binarySearch(a, n, value) {
  let low = 0;
  let high = n - 1;
  while (low <= high) {
    const mid = low + ((high - low) >> 1);
    if (a[mid] > value) {
      if (mid == 0 || a[mid - 1] < value) {
        return mid;
      } else {
        high = mid - 1;
      }
    } else {
      low = mid + 1;
    }
  }
  return -1;
}

查找最后一个小于等于给定值的元素

function binarySearch(a, n, value) {
  let low = 0;
  let high = n - 1;
  while (low <= high) {
    const mid = low + ((high - low) >> 1);
    if (a[mid] > value) {
      high = mid - 1;
    } else {
      if (mid == 0 || a[mid - 1] < value) {
        return mid;
      } else {
        low = mid + 1;
      }
    }
  }
  return -1;
}