文章目录

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

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

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

: 排列相关的搜索问题 ;

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

代码示例 :