二分查找练习总结以及解题模板

二分查找练习总结以及解题模板 二分查找练习总结以及解题模板总结

最近在刷二分查找相关的题，由于二分查找不只限于这一道简单的题，而是一类题的解题思路，因此在这里简单做一个总结。

---

文章目录

• 二分查找练习总结以及解题模板总结
• 一、二分查找的母题
• 二、二分查找思想的使用
• • 1.leetcode 35题
  • 2.leetcode 34题
  • 3.leetcode 69题
  • 4 leetcode 367题
• 总结

---

一、二分查找的母题

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

这是leetcode上的第704题，感兴趣的同学可以去看看具体的题目要求。

二分查找的时间复杂度为o(log n)，查找效率要比遍历高不少，但是用二分查找有两个前提，①有序数组②数组中无重复元素。并不是使用二分这个思想做题就一定得遵循这两条，在后面的题目中有所体现，请耐心看完。

二分查找主要是通过衡量nums[mid]与目标值之间的大小关系，以此判断究竟是将查找区间前移（right = mid - 1）还是后移（left = mid + 1）

这里我给出我的题解：

class Solution {
    public int search(int[] nums, int target) {
        if(target < nums[0] || target > nums[nums.length - 1]){
            return -1;
        }
        int left = 0;
        int right = nums.length - 1;
        while (left <= right){
            int mid = left + ((right - left) >> 1);
            if(nums[mid] == target){
                return mid;
            }else if(nums[mid] < target){
                left = mid + 1;
            }else{
                right = mid - 1;
            }
        }
        return -1;
    }
}

二、二分查找思想的使用

这里着重强调一点，当题目中出现 为无重复元素的升序排列数组或时间复杂度为o(log n)这样的词时，就应该着重考虑二分查找

1.leetcode 35题

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。

这道题如果不加上如果目标值不存在于数组中这句话，那就是二分查找本题了，因此根据题设很自然的联想到使用二分查找。这里需要注意一下，二分查找的本体永远是while循环，且while循环的终止条件永远都是left > right，且最后越界时left都比right大1，然后根据具体题目的要求，看需要返回啥东西，确定while循环结束后return什么即可

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while(left <= right){
			int mid = left + ((right - left) >> 1);
			if(nums[mid] > target){
				right = mid - 1;
			}else if(nums[mid] < target){
				left = mid + 1;
			}else{
			//特殊情况：在数组中找到target，返回相应下标
				return mid;
			}
		}
		//三种情况，target的值不存在于nums中（用一个具体的例子推一下就行）
        //1. 目标值在所有数组元素之前，此时right = -1，left = 0，可以返回left,也可以返回right + 1
        //2. 目标值在所有数组元素之后，此时left = nums.length，right = nums.length - 1，可以返回left,也可以返回right + 1
        //3. 目标值插入在数组中的位置,经过具体场景推导，此时left仍然大于right，因此既可以返回left，也可以返回right + 1
		return left;
    }
}

2.leetcode 34题

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
进阶：
你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？

关键字和O(log n) 再次表明，这道题需要使用二分查找，但实际上这道题我也是理解了别人的题解，然后自己一步一步推出来的（惭愧，刚开始刷题，还是太菜）

以我对这道题的理解所能提供的建议，求左边界和右边界的函数只需从思想上入手，即二分查找的本质，不然从具体推抽象真的不好想

这道题和真正的二分有一个区别，那就是数组可能存在重复元素，且要求这个元素的起始和终止位置，因此就不能在nums[mid] == target时进行return *** 作，分别在求左边界和右边界时和nums[mid] > target 、nums[mid] < target合并。以求左边界为例，在跳出while循环时，left和right所处的位置，left一定是在区间的第一个位置上，right一定在区间的前一个位置上（可以自己举个例子试一下），这也是二分的本质，在跳出二分的while循环时，left一定是在right右边的第一个位置上，这一点多举例子后就能深刻理解。

代码如下：

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int leftborder = leftBorder(nums,target);
        int rightborder = rightBorder(nums,target);
        if(leftborder == -2 || rightborder == -2){
            return new int[]{-1,-1};
        }
        if(rightborder - leftborder > 1){
            return new int[]{leftborder + 1, rightborder - 1};
        }
        return new int[]{-1,-1};
    }
    
    //求左边界
    public int getLeftBorder(int[] nums,int target){
        int left = 0;
        int right = nums.length - 1;
        int leftborder = -2;
        while(left <= right){
            int mid = left + ((right - left) >> 1);
            if(nums[mid] < target){
                //由于数组按照升序排序，此时的nums[mid] < target，相当于mid还在target区间的左边，因此需要将二分搜索区间右移，left = mid + 1;
                left = mid + 1;
            }else{
                //由于数组按照升序排序，此时的nums[mid] >= target，分两种情况讨论
                //在没有了nums[mid] == target -> return mid;这个 *** 作后，当nums[mid] == target时，right会继续右移直至移动到target区间的前一个位置上
                //1. nums[mid] > target,证明mid还在target区间的右边，因此需要将二分搜索区间左移，right = mid - 1，寻找边界
                //2. nums[mid] == target,证明mid已经在target区间的内部，因此需要继续将二分搜索区间左移，right = mid - 1，寻找边界
                right = mid - 1;
                leftborder = right;
            }
        }
        return leftborder;
    }

    //求右边界
    public int getRightBorder(int[] nums,int target){
        int left = 0;
        int right = nums.length - 1;
        int rightborder = -2;
        while(left <= right){
            int mid = left + ((right - left) >> 1);
            if(nums[mid] > target){
                //由于数组按升序排序，此时的nums[mid] > target，相当于mid还在target区间的右边，因此需要将二分搜索区间左移，right = mid - 1
                right = mid - 1;
            }else{
                left = mid + 1;
                rightborder = left;
            }
        }
        return rightborder;
    }
}

3.leetcode 69题

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。

注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
代码如下：

class Solution {
    public int mySqrt(int x) {
        //二分查找法的核心思想实际上是你在用二分之后，需要对找到的数或者该位置的数进行怎样的 *** 作来满足题意，最关键的不是right和left的移动，而是while循环中的if条件判断，需要根据具体的题目场景进行改变，此外return也要根据具体场景变化而变化
        //特殊情况，1和0的平方根是他们自己
        if(x == 1 || x == 0){
            return x;
        }
        int left = 0;
        int right = x;
        while(left <= right){
            int mid = left + ((right - left) >> 1);
            if(mid > x/mid){
                right = mid -1;
            }else if(mid < x/mid){
                left = mid + 1;
            }else{
                return mid;
            }
        }
        return right;
    }
}

4 leetcode 367题

给定一个 正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。

进阶：不要 使用任何内置的库函数，如 sqrt 。

这道题和上道题一样，属于二分查找while循环里if条件随实际题意改变而改变的题，就是判断条件

class Solution {
    public boolean isPerfectSquare(int num) {
        int left = 1;
        int right = num;
        while(left <= right){
            int mid = left + ((right - left) >> 1);
            long sqrt = (long)mid * mid;
            if(sqrt > num){
                right = mid - 1;
            }else if(sqrt < num){
                left = mid + 1;
            }else{
                return true;
            }
        }
        return false;

    }
}

---

总结

当题目中出现有序数组、时间复杂度O(log n)、无重复元素等字眼时，首先考虑二分查找，其次也不是必须无重复元素才能用二分查找，在寻找区间左边界和右边界时可也使用二分查找（34题主要利用了当跳出while循环时，left是比right大1这一条特性的），因此需要灵活使用。此外二分查找的while循环里if的判断条件也不是固定的，随题意的变化而变化，因此要具体问题具体分析（以69题和367题为例）。