二分查找

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法，可以在数据规模的对数时间复杂度内完成查找。
二分查找可以应用于数组，是因为数组具有有随机访问的特点，并且数组是有序的。
二分查找体现的数学思想是「减而治之」，可以通过当前看到的中间元素的特点推测它两侧元素的性质，以达到缩减问题规模的效果。
二分查找问题也是面试中经常考到的问题，虽然它的思想很简单，但写好二分查找算法并不是一件容易的事情。
一分为二，进行元素的查找。我们先看如何来写好二分算法。

关键字

• 查找
• 分割对半
• 中间元素（中间指示符）与左右两侧元素的性质,这个决定 low,height 如何变化

使用前提

• 有序,这个有序是指元素之间构成前后的逻辑关系。如：排序……

组成部分

• 预处理 —— 如果集合未排序，则进行排序。

• 二分查找 —— 使用循环或递归在每次比较后将查找空间划分为两半。

• 后处理 —— 在剩余空间中确定可行的候选者。

模版之间的区别

• 在于后处理问题上

难点

• 如何选用更多的模版，分清模版之间的区别

经典范例

题目：给定一个升序的 nums 数组，和一个 target 值，用二分查找的方式查找该值是否在数组中。

// 二分法查找,前提，有序
function halfSearch(nums, target) {
  let low = 0; //左边界
  let height = nums.length - 1; //右边界
  //划分终止条件，这个是最难的，为什么有个等号，当元素一个的时候, low=0, hight=0,所有还是要判断一下
  while (low <= height) {
    let mid = Math.floor((low + height) / 2); //找中间元素

    // 对每一个中间指标元素都进行了比较，不需要后处理
    if (target === nums[mid]) {
      return mid;
    } else if (target > nums[mid]) {
      low = mid + 1;
    } else if (target < nums[mid]) {
      height = mid - 1;
    }
  }

  return -1;
}

搜索旋转排序数组

这道题的难点，就是 low,hight 的区间缩放。又发现，无论以哪个点做划分，分割出来的，[0,mid][mid,hight],一部分有序，一部分无序， nums[0]<nums[mid]

var search = function (nums, target) {
  /*
    将数组一分为二，其中一定有一个是有序的，另一个可能是有序，也能是部分有序。
    此时有序部分用二分法查找。无序部分再一分为二，其中一个一定有序，另一个可能有序，可能无序。就这样循环. 
  */

  let l = 0;
  let r = nums.length - 1;

  if (nums.length === 1) {
    return nums[0] === target ? 0 : -1;
  }

  while (l <= r) {
    const mid = l + Math.floor((r - l) / 2);

    if (nums[mid] === target) return mid;
    //  难点在这里，分割之后，判断那一边有序，那一边无序
    if (nums[0] <= nums[mid]) {
      // 如果在区间内，
      if (nums[0] <= target && target < nums[mid]) {
        r = mid - 1;
      } else {
        // 不在区间内，导向另一边
        l = mid + 1;
      }
    } else {
      // 如果左边无序，右边有序
      if (nums[mid] < target && target <= nums[nums.length - 1]) {
        l = mid + 1;
      } else {
        //选择左边
        r = mid - 1;
      }
    }
  }

  return -1;
};

注意

• 二分，要注意找到分割的点和区间
• 排序(不一定)好的
• 对谁划分，一定是有序的对象
• 判定
• 初始左右边界
• 中间元素的特点推测它两侧元素的性质

算术 x 平方根 的整数

暴力

1 到 n 这样直接 每个元素与自身相乘，直到第一个大于或者等于的元素截止。

function violenceSqrt(num) {
  let i = 0;

  while (i <= num) {
    if (i * i >= num) {
      if (i * i === num) return i;
      else return i - 1;
    }
    i++;
  }
  return -1;
}

k*k<=x 我们 以 0 ,x 为区间，找中间值的平方

二分法

/**/
function sqrtNumber(num) {
  let i = 0;
  let hight = num;
  while (i <= hight) {
    const mid = (i + hight) >> 1;

    if (mid * mid === num) {
      return mid;
    } else if (mid * mid < num) {
      i = mid + 1;
    } else {
      hight = mid - 1;
    }
  }
  /*
     求5的算数平方根整数
     第一趟 : mid=2    low=3
     第二趟 : mid=4    height=3
     第三趟:  mid=3    3*3>5  所以 hight-1=3-1=2

     循坏中止：low>height 3>2

     可以发现 不相mid*mid!==n，向下取整，hight 就是我们的所求,

     向上取整 low?

  */
  return hight;
}

for (let i = 0; i <= 100; i++) {
  console.log("input" + i, "---val:" + sqrtNumber(i));
}

出题规律

• 求找分界点。非常有用 ，如：第一个错误版本，山脉数组（第一个下降点）

• 一般有序的数组，都可以考虑二分法，或者双指针 :
  如：排序数组的两数之和 https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/
  其基本的思路是，先固定住第一个 数，第二个数，二分查找。。。。。

• 有时候，会给出一个无序的数组，我们可以排序之后，采用二分查找

• 查找某个元素的时候 “我们可以考虑使用二分思想”

• 每次需要查找集合中的索引或元素时，都应该考虑二分查找。如果集合是无序的，我们可以总是在应用二分查找之前先对其进行排序。

计数，后缀和

首先，我们先明白 count 计数的意义：

function specialArray(nums) {
  let n = nums.length;
  let count = new Array(n + 1).fill(0);

  for (let num of nums) {
    // console.log(Math.min(num, n));
    count[Math.min(num, n)]++;
  }
  // console.log(count);
  for (let i = n; i >= 0; i--) {
    if (i < n) count[i] += count[i + 1];
    console.log(i);
    if (count[i] == i) return i;
  }
  return -1;
}

specialArray([0, 4, 3, 0, 4]);

• 模版总结

https://leetcode-cn.com/problems/count-negative-numbers-in-a-sorted-matrix/solution/leetcode-offer-er-fen-cha-zhao-san-da-mo-6rrn/

难点

• 矩阵中的二分查找

https://leetcode-cn.com/problems/kth-smallest-element-in-a-sorted-matrix/

感想，难的太难了….

如何识别二分查找问题

二分法，分界真是太难找了

我并不懂二分查找

左开右闭，什么玩意都不懂呀，这个其实就是判断比较最后一个元素

搜索区间–“不断缩小”，

二分经典题目