【算法】二分法 ② ( 排序数组中查找目标值 | 二分法的经典写法 | 在排序数组中查找元素的最后一个位置 | 二分法的通用模板 )

2023-03-30 18:56:39 浏览数 (1)

文章目录

  • 一、排序数组中查找目标值 ( 二分法的经典写法 )
  • 二、在排序数组中查找元素的最后一个位置 ( 二分法的通用模板 )

一、排序数组中查找目标值 ( 二分法的经典写法 )

https://leetcode.cn/problems/binary-search/

典型的二分查找题目 : 从一个 有序数组 中查找某个 目标值 , 返回 该目标元素在数组中的索引值 , 如果 数组中没有该 目标值 , 则返回 -1 ;

如 : 从 [1 , 2 , 4 , 5 , 6] 中查找 目标值 2 , 返回 2 对应的数组元素索引 为 1 ; 如果从上述数组中查找 3 , 数组中没有该元素 , 则返回 -1 ;

二分法的经典实现 :

代码语言：javascript复制
public class Solution {
    public int search(int[] nums, int target) {
        // 1. 判断参数合法性
        if(nums == null || nums.length == 0) {
            return -1;
        }

        // 2. 二分查找的范围
        int start = 0, end = nums.length - 1;

        // 3. 开始循环进行二分查找
        while(start <= end) {
            // 3.1 计算中间索引
            int mid = start   (end - start) / 2;
            // 3.2 对比中间元素与目标值
            if(nums[mid] == target) {
                // 如果 中心元素 = 目标值 , 找到了目标元素 , 直接返回该索引值
                return mid;
            } else if(nums[mid] > target) {
                // 如果 中心元素 > 目标值 , 则需要去 该查找区间的 左侧继续查找
                end = mid - 1;
            } else {
                // 如果 中心元素 < 目标值 , 则需要去 该查找区间的 右侧继续查找
                start = mid   1;
            }
        }

        // 4. 循环完毕 , 说明最终 start > end , 没有找到目标值
        return -1;
    }
}

上述二分法实现 , 处理 数值没有重复的 数组 中 查找目标值 是可实现的 ;

如果遇到 数组中 要查找的值是重复的 , 要求返回这些数值中的某个指定的索引 , 如 : 返回最后一个 , 返回第一个 , 返回第 n 个 , 等附加要求时 , 上述二分法就无法实现了 ;

二、在排序数组中查找元素的最后一个位置 ( 二分法的通用模板 )

在排序数组中查找元素的最后一个位置 : 从一个 有序数组 中查找某个 目标值 , 返回 该目标元素在数组中的索引值 , 该有序数组中的 元素 可以重复 ,

  • 如果 数组中没有该 目标值 , 则返回 -1 ;
  • 你必须设计并实现 时间复杂度为 O(log n) 的算法解决此问题。

如 : 从 [1 , 2 , 2 , 4 , 5 , 6] 中查找 目标值 2 , 返回 2 对应的数组元素索引 为 1 和 2 , 这里查找的是最后一个位置 , 结果为 2 ; 如果从上述数组中查找 3 , 数组中没有该元素 , 则返回 -1 ;

上述题目要求 时间复杂度 为

O(log n)

, 在上一篇博客 【算法】二分法 ① ( 二分法基本原理简介 | 二分法与哈希表对比 | 常见算法对应的时间复杂度 ) 中提到了常见的算法的时间复杂度如下 , 时间复杂度从小到大进行排序为 :

O(1)

: 位运算 , 哈希表查询

O(log n)

: 二分法 , 快速幂算法 , 辗转相除法 , 倍增法 ;

O(n)

: 枚举法 , 单调栈算法 , 双指针算法 ;

O(n log n)

: 快速排序 , 归并排序 , 堆排序 ;

O(n^2)

: 枚举法 , 动态规划 ;

O(n^3)

: 枚举法 , 动态规划 ;

O(2^n)

: 组合相关的搜索问题 ;

O(n!)

: 排列相关的搜索问题 ;

显然 , 这里需要选择 二分法解决上述算法问题 ;

代码示例 :

代码语言：javascript复制
package cn.zkhw.schedule.utils;

public class Solution {
    public int search(int[] nums, int target) {
        // 1. 判断参数合法性
        if(nums == null || nums.length == 0) {
            return -1;
        }

        // 2. 二分查找的范围
        int start = 0, end = nums.length - 1;

        // 3. 开始循环进行二分查找
        // 此处注意 start 和 end 区间需要能覆盖住所有目标值
        // 该循环条件很重要 , 是通用模板
        // ★ 要点一 : 此处尽量不要使用 start <= end 或 start < end 作为循环判定条件 , 在某些情况下会执行失败
        // 为了让程序有更多的适应性 , 这里使用 start   1 < end 作为循环判定条件 , 可以有效避免死循环
        while(start   1 < end) {
            // 3.1 计算中间索引
            // ★ 要点二 : 此处尽量不要使用 (start   end) / 2 , 如果 两个数值都接近 Int.MAX_VALUE 则会溢出
            int mid = start   (end - start) / 2;
            // 3.2 对比中间元素与目标值
            if(nums[mid] == target) {
                // 如果 中心元素 = 目标值 , 找到了目标元素的第一个位置
                end = mid;
            } else if(nums[mid] > target) {
                // 如果 中心元素 > 目标值 , 则需要去 该查找区间的 左侧继续查找
                // ★ 要点三 : 由于循环判定条件是 start   1 < end , 此处 end 赋值可以不使用 mid - 1
                end = mid;
            } else {
                // 如果 中心元素 < 目标值 , 则需要去 该查找区间的 右侧继续查找
                // ★ 要点四 : 由于循环判定条件是 start   1 < end , 此处 start 赋值可以不使用 mid   1
                start = mid;
            }
        }

        // 4. ★ 要点五 : 循环完毕 , 判定 start 和 end 是不是要找的值
        // 如果数组只有两个数的情况下 
        // while(start   1 < end) 循环控制条件中的 start   1 < end 直接为 false 
        // 循环直接退出 , 此处判定一下 start 和 end 是不是要找的值 
        if(nums[start] == target) {
            return -1;
        }
        if(nums[end] == target) {
            return -1;
        }

        // 5. 没有找到目标值
        return -1;
    }
}
动态规划 排序 数组 算法 索引

0 人点赞