题目描述
示例1:
- 输入: arr = [15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14], target = 5
输出: 8（元素5在该数组中的索引）
示例2:
- 输入：arr = [15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14], target = 11
输出：-1 （没有找到）
提示:
- arr 长度范围在[1, 1000000]之间
解题思路与代码
这道题呢，其实最简单的方法其实就是一个for循环，顺序遍历，直接就解出来了。而且代码的安全性和健壮性也很强，不会有各种各样花里胡哨的错误。
但是呢，顺序遍历的性能呢，在数组较大的情况下可能就没有二分法，那么的好。而这题多半也就是想让你写出二分法的代码。那就如它所愿吧，我们来写一下稍微比较绕的二分法解决办法。
方法一：顺序查找法法
这个方法就一个for循环，我就不献丑写自己的代码了。直接开始讲解二分法的代码
方法二：二分查找法
-
这道题使用的二分法，它其实是分治算法思想的一种体现。分治算法的基本思想就是将一个大问题分解成若干个较小的子问题，然后对这些子问题进行解决，最后将子问题的解合并并得到原始问题的解。
-
在这道题中，我们使用二分法，将数组分成两个部分，每次迭代的时候会去确定目标值是在左半部分，还是在右半部分。然后将搜索范围缩小为相应的部分，并继续重复这个过程，直到找到目标值或者搜索范围为空。
-
这里，我们将大问题（在整个数组中搜索目标值）分解成了较小的子问题（在左半部分还是右半部分搜索目标值），并逐步缩小问题规模，直到找到解决方案。这完美的体现了分钟算法的核心思想。
具体的代码如下：
class Solution {
public:
int search(vector<int>& arr, int target) {
int left = 0;
int right = arr.size() -1;
if(right == -1) return -1;
while(left < right){
int mid = (left + right) / 2 ;
if(arr[left] < arr[mid]){ // 说明左半边是升序
if(arr[left] <= target && arr[mid] >= target) right = mid;
else left = mid + 1;
}else if(arr[left] > arr[mid]){ // 说明左半边不是升序，右半边是升序
if(arr[left] <= target || arr[mid] >= target) right = mid;
else left = mid + 1;
}else { // 可能找到了
if(arr[left] != target) ++left;
else right = left;
}
}
return arr[left] == target ? left : -1;
}
};
复杂度分析
时间复杂度：
- 每次迭代时，我们将搜索范围缩小为原来的一半。因此，最多需要进行 O(log n) 次迭代，其中 n 是数组的长度。在这道题目的特殊情况下，由于可能需要处理重复元素，最坏情况下的时间复杂度会退化为 O(n)（例如，当所有元素都相同时）。然而，在没有重复元素或者重复元素较少的情况下，时间复杂度接近于 O(log n)。
空间复杂度：
- 二分法是在原数组上进行操作的，不需要额外的数据结构来存储子数组。因此，空间复杂度为 O(1)，即常数级别的额外空间。
总结
- 这道题其实可以算是学习二分法或者分治思想的入门题目，还是很有必要去学习和掌握一下的。
觉得我写的还行的小伙伴们请给我点一个赞，你们的赞就是对我持续输出优质内容的最大鼓励，谢谢！