二分查找(704)

一、题目描述

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

示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9     
输出: 4       
解释: 9 出现在 nums 中并且下标为 4     

示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2     
输出: -1        
解释: 2 不存在 nums 中因此返回 -1        

提示:

  • 你可以假设 nums 中的所有元素是不重复的。
  • n 将在 [1, 10000]之间。
  • nums 的每个元素都将在 [-9999, 9999]之间。

二、题目解析

二分查找法有以下几个前提:

  • 1、数组为有序数组
  • 2、数组中不存在重复元素

所以,如果题目中包含以上两个条件,那么就可以思考能否使用二分查找法;相反,如果想使用二分查找法,就得去构造以上这两个条件。

三、参考代码

1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者:程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 二分查找(704):https://leetcode-cn.com/problems/binary-search/ 
class Solution {
    public int search(int[] nums, int target) {

        // 二分查找法的一种写法,在左闭右闭的区间里去查找目标值

        // left 为当前区间最左侧的元素,可以获取到
        int left = 0;

        // right 为当前区间最右侧的元素,可以获取到
        int right = nums.length - 1;


        // 在 while 循环里面,left 不断的 ++,而 right 不断的 --
        // 当 [ left , right ] 这个区间不存在元素的时候,才跳出 while 循环,也就是当 left > right 时跳出循环
        // 即当 left = right + 1 时,搜索区间没有元素了
        // 由于 left 和 right 相遇的时候指向同一个元素,这个元素是存在于 [ left , right] 区间,这个区间就一个元素
        // 所以此时 while 循环的判断可以使用等号
        while(left <= right) {

            // left + (right - left) / 2 和 (left + right) / 2 的结果相同
            // 但是使用 left + (right - left) / 2 可以防止由于 left 、right 同时太大,导致相加的结果溢出的问题
            // 比如数据 int 的最大值为 2,147,483,647
            // 此时,left 为 2,147,483,640
            // 此时,right 为 2,147,483,646
            // 两者直接相加超过了 2,147,483,647,产生了溢出
            int mid = left + (right - left) / 2;

            // 中间的元素和目标值 target 相等,直接返回下标即可
            if(nums[mid] == target) {
                // 直接返回下标即可
                return mid;

            // 中间的元素大于了目标值 target
            // 1、数组为有序数组,比如为递增数组
            // 2、数组中不存在重复元素
            // 由于该数组存在以上两个特点,所以 [ mid , right ] 这个区间中的所有元素都大于目标值 target
            // 因此,缩小查找区间为 [ left , mid - 1]
            } else if(nums[mid] > target) {
                // 也就是说缩小之后的区间最右侧位置为 mid - 1
                right = mid - 1;

            // 中间的元素小于了目标值 target
            // 1、数组为有序数组,比如为递增数组
            // 2、数组中不存在重复元素
            // 由于该数组存在以上两个特点,所以 [ left , mid ] 这个区间中的所有元素都小于目标值 target
            // 因此,缩小查找区间为 [ mid + 1 , right]
            } else if(nums[mid] < target){
                // 也就是说缩小之后的区间最左侧位置为 mid + 1
                left = mid + 1;
            }
        }

        // 查找完区间中的所有元素都没有找到,返回 -1
        return -1;
    }
}

2、C++ 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者:程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 二分查找(704):https://leetcode-cn.com/problems/binary-search/ 
class Solution {
public:
    int search(vector<int>& nums, int target) {

        // 二分查找法的一种写法,在左闭右闭的区间里去查找目标值

        // left 为当前区间最左侧的元素,可以获取到
        int left = 0;

        // right 为当前区间最右侧的元素,可以获取到
        int right = nums.size() - 1;


        // 在 while 循环里面,left 不断的 ++,而 right 不断的 --
        // 当 [ left , right ] 这个区间不存在元素的时候,才跳出 while 循环,也就是当 left > right 时跳出循环
        // 即当 left = right + 1 时,搜索区间没有元素了
        // 由于 left 和 right 相遇的时候指向同一个元素,这个元素是存在于 [ left , right] 区间,这个区间就一个元素
        // 所以此时 while 循环的判断可以使用等号
        while(left <= right) {

            // left + (right - left) / 2 和 (left + right) / 2 的结果相同
            // 但是使用 left + (right - left) / 2 可以防止由于 left 、right 同时太大,导致相加的结果溢出的问题
            // 比如数据 int 的最大值为 2,147,483,647
            // 此时,left 为 2,147,483,640
            // 此时,right 为 2,147,483,646
            // 两者直接相加超过了 2,147,483,647,产生了溢出
            int mid = left + (right - left) / 2;

            // 中间的元素和目标值 target 相等,直接返回下标即可
            if(nums[mid] == target) {
                // 直接返回下标即可
                return mid;

            // 中间的元素大于了目标值 target
            // 1、数组为有序数组,比如为递增数组
            // 2、数组中不存在重复元素
            // 由于该数组存在以上两个特点,所以 [ mid , right ] 这个区间中的所有元素都大于目标值 target
            // 因此,缩小查找区间为 [ left , mid - 1]
            } else if(nums[mid] > target) {
                // 也就是说缩小之后的区间最右侧位置为 mid - 1
                right = mid - 1;

            // 中间的元素小于了目标值 target
            // 1、数组为有序数组,比如为递增数组
            // 2、数组中不存在重复元素
            // 由于该数组存在以上两个特点,所以 [ left , mid ] 这个区间中的所有元素都小于目标值 target
            // 因此,缩小查找区间为 [ mid + 1 , right]
            } else if(nums[mid] < target){
                // 也就是说缩小之后的区间最左侧位置为 mid + 1
                left = mid + 1;
            }
        }

        // 查找完区间中的所有元素都没有找到,返回 -1
        return -1;
    }
};

3、Python 代码

# 登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者:程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 二分查找(704):https://leetcode-cn.com/problems/binary-search/ 
class Solution:
    def search(self, nums: List[int], target: int) -> int:

        # 二分查找法的一种写法,在左闭右闭的区间里去查找目标值

        # left 为当前区间最左侧的元素,可以获取到
        left = 0

        # right 为当前区间最右侧的元素,可以获取到
        right = len(nums) - 1


        # 在 while 循环里面,left 不断的 ++,而 right 不断的 --
        # 当 [ left , right ] 这个区间不存在元素的时候,才跳出 while 循环,也就是当 left > right 时跳出循环
        # 即当 left = right + 1 时,搜索区间没有元素了
        # 由于 left 和 right 相遇的时候指向同一个元素,这个元素是存在于 [ left , right] 区间,这个区间就一个元素
        # 所以此时 while 循环的判断可以使用等号
        while left <= right :

            # left + (right - left) / 2 和 (left + right) / 2 的结果相同
            # 但是使用 left + (right - left) / 2 可以防止由于 left 、right 同时太大,导致相加的结果溢出的问题
            # 比如数据 int 的最大值为 2,147,483,647
            # 此时,left 为 2,147,483,640
            # 此时,right 为 2,147,483,646
            # 两者直接相加超过了 2,147,483,647,产生了溢出
            mid = left + (right - left) // 2

            # 中间的元素和目标值 target 相等,直接返回下标即可
            if nums[mid] == target :
                # 直接返回下标即可
                return mid

            # 中间的元素大于了目标值 target
            # 1、数组为有序数组,比如为递增数组
            # 2、数组中不存在重复元素
            # 由于该数组存在以上两个特点,所以 [ mid , right ] 这个区间中的所有元素都大于目标值 target
            # 因此,缩小查找区间为 [ left , mid - 1]
            elif nums[mid] > target :
                # 也就是说缩小之后的区间最右侧位置为 mid - 1
                right = mid - 1

            # 中间的元素小于了目标值 target
            # 1、数组为有序数组,比如为递增数组
            # 2、数组中不存在重复元素
            # 由于该数组存在以上两个特点,所以 [ left , mid ] 这个区间中的所有元素都小于目标值 target
            # 因此,缩小查找区间为 [ mid + 1 , right]
            elif nums[mid] < target : 
                # 也就是说缩小之后的区间最左侧位置为 mid + 1
                left = mid + 1


        # 查找完区间中的所有元素都没有找到,返回 -1
        return -1

四、动画理解(没有声音)