算法通关村——彻底理解二分查找

布满荆棘的人生 2024-03-23 20:45 47阅读 0赞

## 二分查找的意义 ##

> 请记住凡是涉及到在排好序的地方查找的都就可以考虑用二分来优化查找效率。不一定全局都排好才行，只要某个部分是排好的，就可以针对该部分进行二分查找，这是很多题目优化查找的重要途径。

### 基本查找的缺点 ###

> 查找算法中顺序查找算是最简单的了，无论是有序的还是无序的都可以，也不需要排序，只需要一个个对比即可，但其实效率很低。

#### 方法代码 ####

static  int time = 0;
        public static int commomSearch(int [] arr , int key){
            for (int i = 0; i < arr.length; i++) {
                if (arr[i] == key){
                    time++;
                    return i;
                }
                time ++;
            }
            return -1;
        }

#### 代码测试 ####

public static void main(String[] args) {
            int [] arr = {1,5,3,2,4,8,6,7,9,12,15,18,19};
            int index = commomSearch(arr, 18);
            System.out.println(index == -1 ? "未查询到指定数据,查询了\t"+time+"\t次":"查询到指定数据，其下标为\t"+index+"\t查询了\t"+time+"次");
        }

#### 测试结果 ####

查询到指定数据，其下标为    11    查询了    12次

> 从上述测试结果可知，基本查找是一个一个去查找，查找时与数组元素是否有序无关，虽然实现简单，但是目标值越靠后，效率就越低；而且如果数组中不存在目标值，则会将整个数组遍历一遍，效率太低。

### 二分查找 ###

#### 二分查找与分治的关系 ####

> 在计算机科学中，分治法是一种很重要的算法。字面上的解释是“分而治之”就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题......直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础，如二分搜索、排序算法(快速排序归并排序)等等......  
> 任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小，越容易直接求解，解题所需的计算时间也越少。例如，对于n个元素的排序问题，当n=1时，不需任何计算。n=2时，只要作一次比较即可排好序。n=3时只要作3次比较即可，...。而当n较大时，问题就不那么容易处理了。要想直接解决一个规模较大的问题，有时是相当困难的。
> 
> 二分查找就是将中间结果与目标进行比较，一次去掉一般，因此二分查找可以说是最简单、最典型的分治了。

#### 普通（全局）二分查找 ####

##### 代码实现（循环方式） #####

/*
        二分查找：全局进行二分查找
         */
        public static int binarySearchCommon(int [] arr,int target){
            int low = 0;
            int high = arr.length -1;
            while (low <= high){
                // 这一步很关键
                int mid = low + ((high-low) >>1);
                if (arr[mid] == target){
                    return mid;
                }else if (arr[mid] > target){
                    high = mid - 1;
                }else if (arr[mid] < target){
                    low = mid +1;
                }
            }
            return -1;
        }

#### 指定区域二分查找 ####

##### 代码实现（循环方式） #####

/**
         * 二分查找
         * @param arr 有序数组
         * @param low 左边界
         * @param high 右边界
         * @param target 目标值
         * @return 数组下标
         */
        public static int binarySearch(int [] arr , int low , int high,int target){
            while (low <= high){
                int mid = (low + high) / 2;
                if (arr[mid] == target){
                    return mid;
                }else if (arr[mid] > target){
                    //  因为当前的中间值大于目标值，因此可以舍去中间值的右边部分，即降低high的大小
                    // 由于array[mid]不是目标值，因此再次递归搜索时，可以将其排除，因此需要-1（不考虑当前mid的情况）
                    high = mid -1;
                }else if (arr[mid] < target){
                    //  因为当前的中间值小于目标值，因此可以舍去中间值的左边部分，即提高low的大小
                    // 由于array[mid]不是目标值，因此再次递归搜索时，可以将其排除，因此需要+1（不考虑当前mid的情况）
                    low  = mid + 1;
                }
            }
            return -1;
        }

##### 问题隐患 #####

> 如果指定的low、high的值很大，大到Integer.MAX\_VALUE，如果这样一来，在计算mid的时候就会出现整数溢出的问题（虽然出现机率不大）。因此，为了解决这个问题，通常会采用两种方法
> 
>  *  数学计算法
>  *  移位法
> 
> 这里介绍移位法。对于整数溢出的问题，其实就是在二进制中，原本作为正负标志的符号位由0（正数）变为了1（复数），此时我们进行右移操作，就会将符号位给空出来，自动补0上去，也就解决了溢出问题。同时，在正数的计算中，右移一位 （>>1）和 /2 的效果是一样的，所以可以使用移位的方式解决溢出问题,即 (high + low)>>1。
> 
> 除此之外，还能对(high + low)>>1 优化为 low + ((high-low) >>1)；

#### 指定区域二分查找优化 ####

##### 代码实现 #####

public static int binarySearchOptimize(int [] arr , int low , int high ,int target){
            while (low <= high){
                // 在这里做了优化，防止了整数溢出的问题
                int mid = low + ((high - low) >>1);
                if (arr[mid] == target){
                    return mid;
                }else if (arr[mid] > target){
                    high = mid -1;
                }else if (arr[mid] < target){
                    low = mid +1;
                }
            }
            return -1;
        }

#### 递归方式实现二分查找 ####

##### 代码实现 #####

/*
        递归方式实现二分查找
         */
        public static int binarySearchByRecursion(int [] arr , int low , int high, int target){
            if (low <= high){
                int mid = low + ((high - low) >>1);
                if (arr[mid] == target){
                    return mid;
                }else if (arr[mid] > target){
                    return binarySearchByRecursion(arr, low, mid-1, target);
                }else if (arr[mid] < target){
                    return binarySearchByRecursion(arr, mid +1 , high, target);
                }
            }
            return  -1;
        }

### 二分查找变形之重复元素 ###

#### 问题 ####

>     如果在二分查找中，存在重复元素，如果重复，则找左侧第一个，该怎么做

##### 思路 #####

> 这里的关键是找到目标结果之后不是返回而是继续向左侧移动。第一种，也是最简单的方式，找到相等位置向左使用线性查找，直到找到相应的位置。

#### 代码实现 ####

/**
         *  如果在二分查找中，存在重复元素，如果重复，则找左侧第一个，该怎么做
         * @param arr  有序但含重复元素的数组
         * @param target 目标 值
         * @return 数组下标
         */
        public static int search(int [] arr , int target){
            if (arr == null || arr.length == 0){
                return -1;
            }
            int left = 0;
            int right = arr.length -1;
            while (left <=  right){
                int mid = left + ((right - left) >>1);
                if (arr[mid] > target){
                    right = mid -1;
                }else if (arr[mid] < target){
                    left = mid + 1;
                }else {
                    // 找到之后，继续往左边找，直至找到  与目标元素的重复元素的前一个位置
                    while (mid != 0 && arr[mid] == target){
                        mid -- ;
                    }
                    // 如果重复元素在数组头部分，那就返回重复元素的第一个元素
                    if (mid == 0 && arr[mid] == target){
                        return mid;
                    }
                    // 返回重复元素的第一个元素的下标
                    //注意这里在找到之后的while循环结束后，为什么要返回mid+1，而不是mid呢?
                    // 这是因为此时nums[mid]已经不等于target了，例如假如序列为{1,2,2,22,3,3}，当target=3,当内层的while退出时，nums[mid]=2，因此我们必须返mid+1.
                    return mid+1;
                }
            }
            return -1;
        }

#####  #####