算法小笔记（二分查找）

二分查找：

优势:提高查找效率

前提条件:数据必须是有序的，若数据是乱的，再用二分查找得到的索引没有实际意义，只能确定当前数字在数组中是否存在，因为排序之后的数字的位置就可能发生变化了

过程:

1. min和max表示当前要查找的范围

2. mid是在min和max中间的

3. 若要查找的元素在mid的左边，缩小范围时，min不变，max=mid-1

4. 若要查找的元素在mid的右边，缩小范围时，max不变，min=mid+1

代码实现：

public static int binarySearchBasic(int[] arr, int target) {
​
        int left = 0;
        int right = arr.length - 1;
        while (left  1替换：当要查找的数超过了 int所表示的最大范围，会出现错误（溢出出现负数） 
用无符号右移运算符替换，相当于/2并向下取整
 

问题提出：假设while循环执行L次，如果要查找的元素在最右边，那么代码执行第一个if else比较运算 L次，如果要查找的元素在最左边，先执行第一个if 比较,不满足再执行第二个if 比较运算，一共 2*L 次，左边找的元素和右边找的元素并不是平衡的

改进后代码实现：

 public static int binarySearchBasic(int[] arr, int target) {
        int left = 0;
        int right = arr.length;
        while (1 >> 1;
            if (target  
思路：
 
1.左闭右开的区间，left指向的可能是目标，而right指向的不是目标
 
2.不在循环中找出，等范围内只剩left时，退出循环，在循环外比较a[left]和target的值
 
3.循环内的平均比较次数减少啦
 
4.时间复杂度O(log(n))
 
 
力扣第704题
 
 
二分查找（改动版）:
 
代码实现：
 
public static int binarySearchBasic(int[] arr, int target) {
​
        int left = 0;
        int right = arr.length;     //第一处  int right = arr.length - 1;
        while (left > 1;
​
            if (arr[mid]  
解释：right的含义发生改变，right作为边界使用，它指向的一定不是要查找的目标，它指向的元素一定不会参与比较，left的含义没有发生改变（左闭右开）
 
插值查找:
 
在介绍插值查找之前，先考虑一个问题：
 
为什么二分查找算法一定要是折半，而不是折四分之一或者折更多呢？
 
其实就是因为方便，简单，但是如果我能在二分查找的基础上，让中间的mid点，尽可能靠近想要查找的元素，那不就能提高查找的效率了吗？
 
二分查找中查找点计算如下：
 
 
 
　　mid = (low+high) / 2, 即mid = low + 1 / 2 * (high - low);
 
 
我们可以将查找的点改进为如下：
 
 
 
　　mid = low +(key-a[low]) / (a[high]-a[low]) * (high-low)，
 
 
这样，让mid值的变化更靠近关键字key，这样也就间接地减少了比较次数。
 
要求：数组中的数据分布要比较均匀
 
public static int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        while (left > 1;
            if (target  
力扣第34题
 
还可以改动二分查找Left Most和Right Most 的返回值,让返回值更加有意义
 
Left Most 返回left
 
public static int binarySearchLeftMost(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        while (left >> 1;
            if (target > 1;
            if (target  
来看看改动二分查找Left Most和Right Most 的返回值之后的Left Most和Right Most的几个小应用，先看下面几个名词：
 
 
排名：比如比5小的有5个，所以5的排名就是6
 
前任:比它小的最靠右的
 
后任：比它大的最靠左的
 
最近邻居：看前任后任谁离得更近
 
应用：
 
求排名: binary Search Left Most (target) + 1
 

• target可以存在 binary Search Left Most（4）+ 1 就是 3

• target可以不存在 binary Search Left Most（5）+ 1 就是 6

  求前任： binary Search Left Most（target）- 1

  • target可以存在 binary Search Left Most（4）- 1 就是 1

  • target可以不存在 binary Search Left Most（5）- 1 就是 4

  • 这里的 1 和 4 是下标

    求后任： binary Search Right Most（target）- 1

    • target可以存在 binary Search Right Most（4）+ 1 就是 5

    • target可以不存在 binary Search Right Most（5）+ 1 就是 5

    • 这里的5是下标

      最近邻居：求前任和后任里面最小的

      范围：大于，大于等于，小于，小于等于

      • x=4 : (right Most(4)) ~ 末尾

      • 4