一、是什么

二分查找，亦称折半查找。
它的基本思想是：（这里假设数组元素呈升序排列）将 n 个元素分成个数大致相同的两半，取a[n/2]与欲查找的target作比较，如target = a[n/2]则找到 target，算法终止；如果target < a[n/2]，则我们只要在数组 a的左半部继续搜索 target；如果target > a[n/2]，则我们只要在数组a的右半部继续搜索 target.
通常，二分查找适用于以下几种情况：

  • 有序存储结构，如升序数组、降序数组
  • 按关键字大小有序排列

    二、例题

    1. 二分查找

    :::info 给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
    示例 1:
    输入: nums = [-1,0,3,5,9,12], target = 9
    输出: 4
    解释: 9 出现在 nums 中并且下标为 4
    示例 2:
    输入: nums = [-1,0,3,5,9,12], target = 2
    输出: -1
    解释: 2 不存在 nums 中因此返回 -1 :::

    思路

    通常我们设定左右边界left和right，然后计算左右边界的中间值mid，若nums[mid]小于target，left移动到mid的右侧；若nums[mid]大于target，right移动到mid的左侧；当nums[mid]与target相等的时候，直接返回即可。
    这里我们需要注意几个问题：
  1. 首先，为什么是 while (left <= right) 而不是while (left < right)？
    这是因为要考虑到 left和right 相等的情况，也就是查找区间里只有一个值。
  2. 为什么 left = mid + 1，这个 +1是什么？
    这是因为 mid 位置的值已经查找过了，可以往右边跳一位。
    1. var search = function(nums, target) {
    2.  const len = nums.length
    3.  let left = 0, right = len-1
    4.  while (left <= right) {
    5.      let mid = Math.floor((left+right)/2)
    6.      if (nums[mid] < target) {
    7.          left = mid + 1
    8.      } else if (nums[mid] > target) {
    9.          right = mid - 1
    10.      } else {
    11.          return mid
    12.      }
    13.  }
    14.  return -1
    15. };

    2. Pow(x, n)

    :::info 实现 pow(x, n) ，即计算 x 的 n 次幂函数。 :::

    思路

    这题的第一反应就是一步步用x*x去暴力计算，但是这样子会出现超时。
    所以用一种 快速幂 计算的方式，也就是把 x 的 n 次方转化为 x x 的 n / 2 次方。
    当n为偶数，可以转为`(x    x)^(n/2)；当n为奇数，可以转为x*x^(n-1)`.
    1. var myPow = function(x, n) {
    2.  if (n === 0) return 1
    3.  if (n === 1) return x
    4.  // 先确认n的正负值
    5.  let abs = Math.abs(n)
    6.  const isMinus = abs === n 
    7.  // 如果n/2为偶数，则转换为(x*x)^(n/2)
    8.  // 如果n/2为奇数，则转换为 x * x^(n-1)
    9.  let res = abs % 2 === 0 ? myPow(x*x, abs/2) : x*myPow(x, abs-1)
    10.  // 若n为正数，则直接返回；反之则返回 1/res
    11.  return isMinus ? res : (1/res)
    12. };