牛客网面试必刷：BM17 二分查找-I

曾经终败给现在 2024-03-22 15:13 39阅读 0赞

#### 牛客网面试必刷：BM17 二分查找-I ####

*  前言
 *  一、什么是二分查找？
 *  二、二分查找具体代码
 *   *  1.第一种写法：left <= right
     *  2.第二种写法：left < right
 *  三、复杂度分析

--------------------

## 前言 ##

二分查找是一个常见、基础、难度较低问题，本文记录了我对这个问题的理解，希望能帮助新学者理解

--------------------

## 一、什么是二分查找？ ##

想知道一个数组里（不管是否有序）是否含有一个数字，最简单、最暴力的方法就是利用循环，在数组里面一个一个的验证是否相等，但是这种方法效率很低，面对含有数据很多的数组，非常浪费时间。

二分查找的优势在于可以减少验证结果是否相等的次数，**前提数据是有序的，如果无序则无法使用二分查找**。

**二分查找具体步骤为：**

step 1：从数组首尾开始，每次取中点值。
    step 2：如果中间值等于目标即找到了，可返回下标，如果中点值大于目标，说明中点以后的都大于目标，因此目标在中点左半区间，如果中点值小于目标，则相反。
    step 3：根据比较进入对应的区间，直到区间左右端相遇，意味着没有找到

**常见题目为：**

**请实现无重复数字的升序数组的二分查找：**  
**给定一个 元素升序的、无重复数字的整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标（下标从 0 开始），否则返回 -1**

## 二、二分查找具体代码 ##

二分查找的代码有多种写法，最关键的其实就是循环条件的确定，也就是 left 和 right 的比较。

理论上来说，left < right 和 left <= right 两种写法都可以，关键是需要明确思路

### 1.第一种写法：left <= right ###

这种写法在我看来是最容易理解，最好写的，我个人也比较推荐这种

代码如下（示例）：

/**
         * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
         *
         * 
         * @param nums int整型一维数组 
         * @param target int整型 
         * @return int整型
         */
        public int search (int[] nums, int target) {
        
            // write code here
            int left = 0;
            int right = nums.length - 1 ;
            while(left <= right){
        
              // mid = (right - left)/2 + left;是为了防止 right + left 超过 int 的取值范围而报错
                int mid = (right - left)/2 + left;
                if(nums[mid] < target){
        
                    left = mid + 1;
                }else if(nums[mid] > target){
        
                    right = mid - 1;
                }else{
        
                    return mid;
                }
            }
            return -1;
        }

**核心思想：left <= right 实际上是取 \[left,right\] ，也就是左右闭区间，所以当nums\[mid\] < target 的时候，left = mid + 1，也就是说 nums\[mid\] 不需要带入到下次循环中了，因为检索范围是 \[left,right\] ；**

**同理，当nums\[mid\] > target的时候，right = mid - 1。**

**一句话总结：nums\[mid\] < target 的时候，left = mid + 1；nums\[mid\] > target的时候，right = mid - 1。一开始的时候，right = nums.length - 1**

### 2.第二种写法：left < right ###

这种写法也可以，但是理解起来要稍微困难一点

代码如下（示例）：

/**
         * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
         *
         * 
         * @param nums int整型一维数组 
         * @param target int整型 
         * @return int整型
         */
        public int search (int[] nums, int target) {
        
            // write code here
            int left = 0;
            int right = nums.length;
            while(left < right){
        
            // mid = (right - left)/2 + left;是为了防止 right + left 超过 int 的取值范围而报错
                int mid = (right - left)/2 + left;
                if(nums[mid] < target){
        
                    left = mid + 1;
                }else if(nums[mid] > target){
        
                    right = mid;
                }else{
        
                    return mid;
                }
            }
            return -1;
        }

**核心思想：left < right 实际上是取 \[left,right） ，也就是左闭右开区间，所以当 nums\[mid\] < target 的时候，left = mid + 1，也就是说 nums\[mid\] 不需要带入到下次循环中了，因为检索范围是 \[left,right）；**

**关键点1：然而，当nums\[mid\] > target的时候，right = mid ，因为区间为左闭右开，只有 right = mid 的时候才符合搜索要求， right = mid 不会导致nums\[right\] 的值被检索到**

**关键点2：left < right 的时候，right = nums.length ，而 left <= right 的时候，right = nums.length - 1。**  
**原因就是：left < right 的时候检索的是 \[left,right），left <= right 的时候检索的是 \[left,right\] ，需要好好理解这二者的区别**

**一句话总结：nums\[mid\] < target 的时候，left = mid + 1；nums\[mid\] > target的时候，right = mid。同时，一开始的时候，right = nums.length**

## 三、复杂度分析 ##

![在这里插入图片描述][da1af407aa6e49b1980e5f53646e8d22.png]

[da1af407aa6e49b1980e5f53646e8d22.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/507045eb686340e5b967dbbab86eb463.png