无处不在的二分查找？

1 二分查找在实际中应用的很多，但是思想确实很简单，就是类似于分治的思想，比如你想从1000甚至更多的数字中寻找特定的数，如果你挨个去查找，当然可以，但是如果可以每次查找就可以确定想要查找的数不在另外一半中，是不是要快很多。

二分查找就是这么简单，只要记住，找到方法可以把范围缩小一半，就可以使用二分查找。

69 求开方

题目描述

给定一个非负整数，求它的开方，向下取整。

例子1

输入: 8
输出: 2
解释: 8 的开方结果是 2.82842...，向下取整即是 2。

例子2

输入: 4
输出: 2
解释: 4 的开方结果是 2。

说明
0 <= x <= 2^31 - 1

思考 1

这个思路很简单，因为是求n的开方，可以查找1到n/2的数字， 这里就可以使用二分查找，如果发现等于n，则返回，如果大于n，则可以在比较小的一半中查找，如果发现小于n，则可以在比较大的一半中查找

当然这个题目还有其他的数学解法，这里我们只是了解二分查找的思想，其他的数学解法，可以自己去了解。

实现1

/**
 * @param {number} x
 * @return {number}
 */
export default (x) => {
  const halfX = Math.ceil(x / 2);
  let low = 1;
  let high = halfX;
  while (low <= high) {
    let mid = Math.floor(low + (high - low) / 2);
    if (mid * mid === x) {
      return mid;
    } else if (mid * mid < x) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }
  return low * low > x ? low - 1 : low + 1;
};

复制代码

算法时间复杂度 O(lgn/2), 空间复杂度 O(1)

34 查找区间

题目描述

给定一个增序的整数数组和一个值，查找该值第一次和最后一次出现的位置。如果不存在该值，则两个返回值都设为-1

进阶
使用O（lgn）时间复杂度解决。

例子1

输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]
解释: 数字 8 在第 3 位第一次出现，在第 4 位最后一次出现。

例子2

输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]
解释: 6 在数组中没有出现

例子3

输入: nums = [3,3,3], target = 3
输出: [0,2]
解释: 3 在数组中出现第一次位置是0，最后一次的位置2

说明
1 0 <= nums.length <= 10^5
2 -10^9 <= nums[i] <= 10^9
3 -10^9 <= target <= 10^9

思考 1

这个思路很简单，因为数组是升序的，而且指明使用O（lgn）方法解决，很明显使用二分查找解决。

这个也比较简单，就是常用的二分查找，如果最后没有发现，返回[-1,-1]就可以了

这里需要注意的就是你要找到target在数组中第一出现的位置和target最后一次出现的位置。

实现1

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
export default (nums, target) => {
  if (nums.length === 0 || (nums.length === 1 && nums[0] !== target)) {
    return [-1, -1];
  }
  if (nums.length === 1 && nums[0] === target) {
    return [0, 0];
  }

  const len = nums.length;
  let low = 0;
  let high = len - 1;

  const res = [];
  while (low <= high) {
    // 为了防止数据溢出
    let mid = Math.floor(low + (high - low) / 2);

    if (nums[mid] === target) {
      let minFlag = false;
      let maxTemp = mid;
      let minTemp = mid;
      while (minTemp >= 0 && nums[minTemp] === target) {
        minTemp--;
      }

      if (minTemp + 1 !== mid) {
        res.push(minTemp + 1);
      } else {
        res.push(mid);
      }
      while (maxTemp < len && nums[maxTemp] === target) {
        maxTemp++;
      }

      if (maxTemp === mid + 1) {
        res.push(mid);
      } else {
        res.push(maxTemp - 1);
      }
      return res;
    }
    if (nums[mid] < target) {
      low = mid + 1;
    }
    if (nums[mid] > target) {
      high = mid - 1;
    }
  }
  if (res.length === 2) {
    return res.sort((a, b) => a - b);
  } else {
    return [-1, -1];
  }
};

复制代码

算法时间复杂度 O(lgn), 空间复杂度 O(1)

81 旋转数组查找数字

题目描述

一个原本增序的数组被首尾相连后按某个位置断开(如 [1,2,2,3,4,5] → [2,3,4,5,1,2]，在第一 位和第二位断开)，我们称其为旋转数组。给定一个值，判断这个值是否存在于这个旋转数组中。如果存在返回true，如果不存在返回false

例子1

输入: nums = [2,5,6,0,0,1,2], target = 0
输出: true

例子2

输入: nums = [2,5,6,0,0,1,2], target = 3
输出: false

思考 1

最简单的肯定直接遍历数组，不过这里显然不使用这种

可以看到数组是一部分升序，另外一部分也是升序，问题是如何找到在哪里分割开？

当然这里可以遍历数组，找到分割开的两个升序数组，但是这样那不如直接遍历，不用二分查找了。

那么是否可以换个角度，假设我们如果直接使用二分查找，会怎么样呢？

可以想一下

刚开始我是想根据mid和mid+1的关系来决定移动low和high或者根据mid和mid-1的关系来决定移动low和high，可是这样感觉逻辑很复杂

后来看了题解，才明白可以把mid和low和high的关系来移动指针，如果nums[mid] 小于nums[high],那肯定是升序，因为问的数组是升序的，如果target在这个升序数组中，那么就可以排除另一半了

当nums[mid] 大于nums[low]的时候，说明这也是一个派序数组，如果同时target在这个排序数组呢，同时也能排除另外一半数组了

这里还有另外一种情况，因为数组中存在重复的数字，如果发现nums[mid]等于num[low]，此时我们可以把low++，重新计算mid，计算target存在的范围

当nums[mid]等于num[high]，此时我们可以把high，重新计算mid，计算target存在的范围

但是运行之后，可以发现这里的二分查找和遍历数组使用时间基本差不多。

实现1

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {boolean}
 */
export default (nums, target) => {
  if (nums.length === 0 || !nums) {
    return false;
  }
  if (nums.length === 1) return nums[0] === target;

  let low = 0;
  let high = nums.length - 1;
  while (low <= high) {
    let mid = Math.floor(low + (high - low) / 2);
    if (nums[mid] === target) {
      return true;
    }
    if (nums[mid] < nums[high]) {
      // 判断target是否在这个范围内
      if (target > nums[mid] && target <= nums[high]) {
        low = mid + 1;
      } else {
        high = mid - 1;
      }
    } else if (nums[mid] > nums[low]) {
      if (target >= nums[low] && target < nums[mid]) {
        high = mid - 1;
      } else {
        low = mid + 1;
      }
    } else if (nums[low] === nums[mid]) {
      low++;
    } else {
      high--;
    }
  }
  return false;
};


复制代码

算法时间复杂度 O(n),因为最坏的情况下，二分查找就变成了遍历数组了。 空间复杂度 O(1)

154 旋转数组查中寻找最小的元素

题目描述

假设一个排好序的数组在某处执行了一次“旋转”，找出最小的元素（数组元素可能重复），数组中包含重复数字

例子1

输入: [1,3,5]
输出: 1

例子2

输入: [2,2,2,0,1]
输出: 0

例子3

输入: [3,3,1,3]
输出: 1

例子4

输入: [10,1,10,10,10]
输出: 1

思考 1

这里和上面的81题目有点类似，应该可以采用同样的策略，只不过是把81的题目的target变成了最小的数字,思路基本类似。

另外说一下，这题在leetcode上标记为hard，但是81题标记为medium，但是两者的难度差不多，所以有时候，没有必要对题目的难度过于太在意

实现1

/**
 * @param {number[]} nums
 * @return {number}
 */
// 2, 2, 2, 0, 1;
export default (nums) => {
  if (nums.length === 0 || !nums) {
    return false;
  }
  if (nums.length === 1) return nums[0];
  let low = 0;
  let high = nums.length - 1;
  let min = Number.MAX_VALUE;
  while (low <= high) {
    let mid = Math.floor(low + (high - low) / 2);
    if (nums[mid] < nums[high]) {
      high = mid - 1;
      min = Math.min(nums[mid], min);
    } else if (nums[mid] > nums[low]) {
      min = Math.min(nums[low], min);
      low = mid + 1;
    } else if (nums[low] === nums[mid]) {
      min = Math.min(nums[low], min);
      low++;
    } else {
      min = Math.min(nums[high], min);
      high--;
    }
  }
  return min;
};



复制代码

算法时间复杂度 O(n),因为最坏的情况下，二分查找就变成了遍历数组了。 空间复杂度 O(1)

540. 有序数组中的单一元素

题目描述

给定一个只包含整数的有序数组，每个元素都会出现两次，唯有一个数只会出现一次，找出这个数。

例子1

输入: [1,1,2,3,3,4,4,8,8]
输出: 2

例子2

输入: [3,3,7,7,10,11,11]
输出: 10

注意: 您的方案应该在 O(log n)时间复杂度和 O(1)空间复杂度中运行。

思考 1

很简单，用二分查找就可以,要点就是因为数组中除了一个数字，其它的数字都是出现两次，所以可以根据mid的下标是奇数或者偶数来判断数字是否出现在那一侧

如果mid是偶数，那说明low到mid有奇数个数字，所以就可以判断nums[mid] 和nums[mid-1]是否相等，来判断只出现一次的数字是否出现在这一侧。

思路比较简单

实现1

/**
 * @param {number[]} nums
 * @return {number}
 */

export default (nums) => {
  if (nums.length === 1) return nums[0];
  let low = 0;
  let high = nums.length - 1;
  while (low <= high) {
    let mid = Math.floor(low + (high - low) / 2);
    console.log(low, high, mid);
    if (
      (mid + 1 < nums.length && nums[mid] !== nums[mid + 1] && mid >= 1 && nums[mid] !== nums[mid - 1]) ||
      (mid === nums.length - 1 && nums[mid] !== nums[mid - 1]) ||
      (mid === 0 && nums[mid] !== nums[mid + 1])
    ) {
      return nums[mid];
    }
    if (mid % 2 !== 0) {
      if (mid >= 1 && nums[mid - 1] === nums[mid]) {
        low = mid + 1;
      } else {
        high = mid - 1;
      }
    } else {
      if (mid >= 1 && nums[mid] === nums[mid - 1]) {
        high = mid - 1;
      } else {
        low = mid + 1;
      }
    }
  }
  return nums[low];
};

};



复制代码

算法时间复杂度 O(lgn)。 空间复杂度 O(1)

4. 寻找两个正序数组的中位数

题目描述

给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。

进阶：你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？

例子1

输入: nums1 = [1,3], nums2 = [2]
输出: 2.00000
解释：合并数组 = [1,2,3] ，中位数 2

例子2

输入: nums1 = [1,2], nums2 = [3,4]
输出: 2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

例子3

输入: nums1 = [0,0], nums2 = [0,0]
输出: 0.00000

例子4

输入: nums1 = [], nums2 = [1]
输出: 1.00000

例子5

输入: nums1 = [2], nums2 = []
输出: 2.00000

提示：
1 nums1.length == m
2 nums2.length == n
3 0 <= m <= 1000
4 0 <= n <= 1000
5 1 <= m + n <= 2000
6 -10^6 <= nums1[i], nums2[i] <= 10^6

思考 1

题目如果第一次见到，很难想出如何使用二分查找的，不过也可以思考试试

首先判断nums1和nums2的数组长度，让nums1的数组长度小于等于nums2的数组长度

假设k是nums1和nums2合并之后，我们要寻找的中位数下标，这里如果nums1和nums2合并后的长度是奇数，我们可以寻找 k = left的数字

const left = Math.floor((nums1Len + nums2Len + 1) / 2)
复制代码

如果nums1和nums2合并后的长度是偶数，我们可以分别寻找合并后的数组中下标分别是下面这两个位置的，也就是寻找k = left和k=right两个位置的数字

const left = Math.floor((nums1Len + nums2Len + 1) / 2);
  const right = Math.floor((nums1Len + nums2Len + 2) / 2);
复制代码

原理很简单，我们先从nums1中拿出k/2个数字和从nums2中拿出k/2个数字，如果nums1[k/2] 大于nums2[k/2],那么我们要寻找的k位置的数字，肯定在nums1和nums2除去0到k/2的数组中。

因为nums1[k/2]大于nums2[k/2]，所以就可以排除nums[k/2]之前的数字，但是我们不知道nums1的数字是否都大于nums2[k/2]，所以可以在剩下的数组中寻找排在k/2位置的数字。

实现1

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
const getKth = (nums1, start1, end1, nums2, start2, end2, k) => {
  const len1 = end1 - start1 + 1;
  const len2 = end2 - start2 + 1;
  // 如果nums1的长度大于nums2的长度，改变两个数组的位置, 让数组长度最小的在前面，防止
  // 这里的nums2[start2 + k - 1]报错
  if (len1 > len2) return getKth(nums2, start2, end2, nums1, start1, end1, k);
  if (len1 === 0) return nums2[start2 + k - 1];
  if (k === 1) return Math.min(nums1[start1], nums2[start2]);

  const i = start1 + Math.min(len1, Math.floor(k / 2)) - 1;
  const j = start2 + Math.min(len2, Math.floor(k / 2)) - 1;

  const nums1End = Math.min(end1, i + 1);
  const nums2End = Math.min(end2, j + 1);
  if (nums1[i] > nums2[j]) {
    return getKth(nums1, start1, nums1End, nums2, j + 1, end2, k - (j - start2 + 1));
  } else {
    return getKth(nums1, i + 1, end1, nums2, start2, nums2End, k - (i - start1 + 1));
  }
};
export default (nums1, nums2) => {
  if (nums1.length === 0 && nums2.length === 1) {
    return nums2[0];
  }
  if (nums1.length === 1 && nums2.length === 0) {
    return nums1[0];
  }
  const nums1Len = nums1.length;
  const nums2Len = nums2.length;
  // 分别找到奇数和偶数的中位数的左边和右边
  const left = Math.floor((nums1Len + nums2Len + 1) / 2);
  const right = Math.floor((nums1Len + nums2Len + 2) / 2);
  // 如果是奇数，只寻找一次就可以了
  if ((nums1Len + nums2Len) % 2 !== 0) {
    return getKth(nums1, 0, nums1Len - 1, nums2, 0, nums2Len - 1, left);
  }
  return (
    (getKth(nums1, 0, nums1Len - 1, nums2, 0, nums2Len - 1, left) +
      getKth(nums1, 0, nums1Len - 1, nums2, 0, nums2Len - 1, right)) *
    0.5
  );
};

复制代码

算法时间复杂度也很容易理解
m 是nums1.length，n 是nums2.length 因为每次查找的范围都从(m+n)/2 缩小一半范围。所以时间复杂度是O(lg(m+n))
空间复杂度 O(lg(m+n))

二分查找算法总结

二分查找其实就是一个分值思想，如果你可以根据一些条件，每次缩小一半的查找范围，基本就可以确定使用二分查找。

不过有些可能不是很明显，可能需要经过转化处理，不过核心就是可以不断的缩小查找范围，让我们离答案更近一下。