每日一题-二分查找
二分查找实现：寻找目标值在升序数组中的位置
题目描述
给定一个元素升序的、无重复数字的整型数组 nums 和一个目标值 target，实现一个函数，在数组中查找目标值，如果目标值存在则返回其下标（下标从0开始），否则返回 -1。
函数签名
int search(int* nums, int numsLen, int target);
输入
nums：一个整数数组，数组中的元素为升序排列且没有重复元素。numsLen：整数，数组nums的长度。target：目标整数，表示需要在数组中查找的数值。
输出
- 返回目标值
target在数组nums中的下标。如果目标值不存在，返回-1。
数据范围
- 数组长度：$ 0 \leq len(nums) \leq 2 \times 10^5 $
- 数组元素范围：$ |val| \leq 10^9 $
进阶要求
- 时间复杂度：$ O(\log n) $
- 空间复杂度：$ O(1) $
示例
示例1
输入：
int nums[] = {-1, 0, 3, 4, 6, 10, 13, 14};
int target = 13;
输出：
6
说明：13 出现在数组 nums 中且下标为6。
示例2
输入：
int nums[] = {};
int target = 3;
输出：
-1
说明：数组为空，返回 -1。
示例3
输入：
int nums[] = {-1, 0, 3, 4, 6, 10, 13, 14};
int target = 2;
输出：
-1
说明：2 不存在数组 nums 中，因此返回 -1。
解题思路
由于数组是升序且无重复的，我们可以使用二分查找来提高搜索效率。二分查找的时间复杂度为 $ O(\log n) $，符合题目要求。
代码实现
/**
* 实现二分查找，寻找目标值在数组中的位置
*
* @param nums int整型一维数组，升序且无重复
* @param numsLen int nums数组长度
* @param target int 目标值
* @return int 目标值在数组中的下标，如果不存在返回 -1
*/
int search(int* nums, int numsLen, int target) {
// 初始化左右指针，分别指向数组的开头和结尾
int left = 0;
int right = numsLen - 1;
// 开始二分查找循环
while (left <= right) {
// 计算中间位置，避免 (left + right) 可能出现的溢出
int mid = left + (right - left) / 2;
// 判断中间值是否等于目标值
if (nums[mid] == target) {
return mid; // 找到目标值，返回下标
} else if (nums[mid] < target) {
// 如果中间值小于目标值，说明目标值在右半部分
left = mid + 1;
} else {
// 如果中间值大于目标值，说明目标值在左半部分
right = mid - 1;
}
}
// 如果退出循环，说明没有找到目标值
return -1;
}
代码解析
-
初始化左右指针：
left初始化为 0，right初始化为numsLen - 1，分别指向数组的开头和结尾。 -
二分查找过程：
通过计算mid = left + (right - left) / 2来避免可能的溢出，查找数组中间的元素。如果nums[mid] == target，则返回mid。如果nums[mid] < target，目标值在右侧，更新left = mid + 1；如果nums[mid] > target，目标值在左侧，更新right = mid - 1。 -
查找结束：
如果循环结束仍未找到目标值，返回-1。
时间复杂度
- 每次查找都将查找范围缩小一半，因此时间复杂度为 $ O(\log n) $。
空间复杂度
- 只使用了常数空间来存储指针和中间值，因此空间复杂度为 $ O(1) $。
总结
最开始我还想着，除以二余数的问题，但是后来才想到，其实本质上就是层层靠近的问题，每一次更新后，leaf或者right铁定更加靠近目标值，所以根本不用担心靠近的问题。
原文地址：https://blog.csdn.net/zxjiaya/article/details/145247263
免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！