[数据结构与算法]12 你可能知道二分查找,但你肯定不知道还有这样的二分查找!

秒速五厘米 2023-07-17 04:37 8阅读 0赞

对于二分查找,应该不是很陌生.  
比如,我写了一个数字 23 ,让你在 0-99 里面猜,猜大了或者猜小了我会告诉你,直到猜对为止.  
为了尽快猜对,你是不是会这样猜?

# 代码实现 #

看起来这个过程蛮简单的,代码实现也挺简单的:

/** * 二分查找 * @author 郑璐璐 * @date 2020-3-20 20:01:46 */
    public class Binary { 
        /** * 二分查找 * @param arr 传入的数组 * @param n 数组的长度 * @param value 要查找的值 * @author 郑璐璐 * @date 2020-3-20 20:03:56 */
        public static int binarySearch(int[] arr, int n, int value){ 
            int low = 0;
            int high = n-1;
    
            while (low <= high){ 
                int mid = low + (( high - low) >> 1);
                if ( arr[mid] == value){ 
                    return mid;
                }else if( arr[mid] < value){ 
                    low = mid + 1;
                }else{ 
                    high = mid - 1;
                }
            }
            return -1;
        }
        public static void main(String[] args){ 
            int[] arr ={ 1,8,13,25,27,30,37,47,66,95};
    
            // 调用 BinarySearch 
            int binarySearch = binarySearch(arr,arr.length,95);
    
            System.out.println(binarySearch);
        }
    }

在写二分查找时,注意三点写出的代码就差不了多少:

*  循环退出条件  
    注意是 low <= high ; 而不是 low < high .
 *   mid 的取值  
    这里 mid = low + (( high - low)>>1) 这种方式是将除以 2 的操作转化成了位运算,这样对于计算机来说处理速度会更快一些
 *   low 和 high 的更新  
    low = mid + 1; high = mid - 1; 不要写成 low = mid 或者 high = mid ,因为假设 high = 5 , low = 5 时, arr\[5\] 可能不等于 value ,这样就会导致程序陷入死循环.

# 二分查找适用场景 #

二分查找的时间复杂度是 O(log n),查找数据的效率很高,但是不是什么情况下都可以使用二分查找.  
首先,二分查找依赖的是顺序表结构,也就是数组.  
它可以依赖其他数据结构嘛?比如链表?答案是不能,因为二分查找算法需要按照下标随机访问元素,而链表不能做到.

其次,二分查找针对的是已经排好序的数据.  
如果想要使用二分查找,那么数据必须是有序的.  
数据无序怎么办?那就先排好序咯~  
否则的话,有可能导致查找不到你想要的数据(不信可以试试,事实会告诉你真相的~  
那么,既然要求数据有序,所以如果应用场景是频繁对数据进行插入,删除的话,想都不用想,不适合使用二分查找

最后,数据量如果太小的话,不适合二分查找.  
如果要处理的数据量非常小,直接顺序遍历就可以了,完全没有必要使用二分查找.  
什么都会有个度,所以数据量如果太大的话,也不适合二分查找.

# 二分查找的一些变形 #

OK ,在掌握基础的二分查找之后,咱们来对它进行一下变形  
因为比较简单而且容易理解,我就直接上代码了~

## 查找第一个值等于给定值的元素 ##

/** * 二分查找---查找第一个值等于给定值的元素 * @param arr 传入的数组 * @param n 数组的长度 * @param value 要查找的值 * @author 郑璐璐 * @date 2020-3-20 20:32:54 */
        public static int searchEqualFirst(int[] arr,int n, int value){ 
            int low = 0;
            int high = n-1;
            while (low <= high){ 
                int mid = low + ((high - low) >> 1);
                if (arr[mid]>value){ 
                    high = mid - 1;
                }else if (arr[mid] < value){ 
                    low = mid + 1;
                }else{ 
                    // 如果 mid 等于 0 ,说明这个元素是数组的第一个元素
                    // 或者 arr[mid-1] 不等于要查找的值,说明此时查找到的元素即为第一个找到等于给定值的元素
                    if ((mid == 0)|| (arr[mid - 1] != value)) { 
                        return mid;
                    } else { 
                        high = mid - 1;
                    }
                }
            }
            return -1;
        }

## 查找最后一个值等于给定值的元素 ##

/** * 二分查找---查找最后一个值等于给定值的元素 * @param arr 传入的数组 * @param n 数组的长度 * @param value 要查找的值 * @author 郑璐璐 * @date 2020-3-20 20:39:14 */
        public static int searchEqualFinal(int[] arr,int n, int value){ 
            int low = 0;
            int high = n-1;
            while (low <= high){ 
                int mid = low + ((high-low) >> 1);
                if (arr[mid] > value){ 
                    high = mid - 1;
                }else if (arr[mid] < value){ 
                    low = mid + 1;
                }else{ 
                    if ((mid == n-1) || (arr[mid+1] != value)){ 
                        return mid;
                    } else { 
                        low = mid + 1;
                    }
                }
            }
            return -1;
        }

## 查找第一个大于等于给定值的元素 ##

/** * 二分查找---查找第一个大于等于给定值的元素 * @param arr 传入的数组 * @param n 数组的长度 * @param value 要查找的值 * @author 郑璐璐 * @date 2020-3-20 20:47:46 */
        public static int searchFirst(int[] arr, int n, int value){ 
            int low = 0;
            int high = n-1;
            while (low <= high){ 
                int mid = low + ((high - low) >> 1);
                if (arr[mid] >= value){ 
                    if ((mid == 0) || (arr[mid - 1] < value)){ 
                        return mid;
                    } else{ 
                        high = mid -1;
                    }
                }else{ 
                    low = mid + 1;
                }
            }
            return -1;
        }

## 查找最后一个小于等于给定值的元素 ##

/** * 二分查找---查找最后一个小于等于给定值的元素 * @param arr 传入的数组 * @param n 数组的长度 * @param value 要查找的值 * @author 郑璐璐 * @date 2020-3-20 20:54:52 */
        public static int searchFinal(int[] arr, int n, int value){ 
            int low = 0;
            int high = n-1;
            while (low <= high){ 
                int mid = low + ((high - low) >> 1);
                if (arr[mid] > value){ 
                    high = mid -1;
                }else { 
                    if ((mid == n-1) || (arr[mid + 1] > value)){ 
                        return mid;
                    }else{ 
                        low = mid + 1;
                    }
                }
            }
            return -1;
        }

*  参考  
    极客时间<数据结构与算法之美>

以上,感谢您的阅读~