1-数组-11-二分查找-LeetCode704
参考:代码随想录
LeetCode:题目序号35
更多内容欢迎关注我(持续更新中,欢迎Star✨)
Github:CodeZeng1998/Java-Developer-Work-Note
技术公众号:CodeZeng1998(纯纯技术文)
生活公众号:好锅(Life is more than code)
博客园: CodeZeng1998
其他平台:CodeZeng1998、好锅
题目描述:
给定一个 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]
之间。
二分查找(左闭右闭)
/**
* 二分查找(左闭右闭)
*
* @param nums 升序排序的数组
* @param target 目标值
* @return 数组索引,如果未找到则返回 -1
* @Author: CodeZeng1998
*/
public int binarySearch(int[] nums, int target) {
if (target < nums[0] || target > nums[nums.length - 1]) {
return -1;
}
int left = 0;
int right = nums.length - 1;
while (left <= right) {
// 当 left、right为较大整数时可能出现溢出,防止溢出,等同于(left + right)/2
int middle = left + ((right - left) >> 1);
if (nums[middle] > target) {
right = middle - 1;
} else if (nums[middle] < target) {
left = middle + 1;
} else {
return middle;
}
}
return -1;
}
ChatGPT:
这段代码实现了一个二分查找算法,用于在升序排序的数组中查找目标值。以下是代码的解释:
nums
:升序排序的整数数组。target
:要查找的目标值。- 方法返回目标值在数组中的索引,如果未找到则返回 -1。
算法步骤如下:
- 首先,检查目标值是否小于数组的第一个元素或大于数组的最后一个元素,如果是,则返回 -1,因为目标值不可能存在于数组中。
- 使用两个指针
left
和right
分别指向数组的开头和结尾。 - 进入循环,当
left
小于等于right
时进行查找。 - 计算中间索引
middle
,采用了防止整数溢出的方式计算,即left + ((right - left) >> 1)
。 - 如果
nums[middle]
大于目标值target
,则更新right
为middle - 1
,因为目标值可能在左半部分。 - 如果
nums[middle]
小于目标值target
,则更新left
为middle + 1
,因为目标值可能在右半部分。 - 如果
nums[middle]
等于目标值target
,则直接返回middle
,表示找到了目标值的索引。 - 如果循环结束仍未找到目标值,则返回 -1,表示未找到目标值。
这个算法的时间复杂度为 O(log n),其中 n 是数组的长度,因为每次查找都将搜索范围减半。
二分查找(左闭右开)
/**
* 二分查找(左闭右开)
*
* @param nums 升序排序的数组
* @param target 目标值
* @return 数组索引,如果未找到则返回 -1
* @author CodeZeng1998
*/
public int binarySearch(int[] nums, int target) {
int left = 0;
// 定义target在左闭右开的区间里,即:[left, right)
int right = nums.length;
// 因为left == right的时候,在[left, right)是无效的空间,所以使用 <
while (left < right) {
// 当 left、right为较大整数时可能出现溢出,防止溢出,等同于(left + right)/2
int middle = left + ((right - left) >> 1);
if (nums[middle] > target) {
right = middle;
} else if (nums[middle] < target) {
left = middle + 1;
} else {
return middle;
}
}
return -1;
}
GhatGPT:
这段代码实现了一个二分查找算法,与之前的代码相比,不同之处在于区间的定义是左闭右开的 [left, right)
,而不是左闭右闭的 [left, right]
。以下是代码的解释:
nums
:升序排序的整数数组。target
:要查找的目标值。- 方法返回目标值在数组中的索引,如果未找到则返回 -1。
算法步骤如下:
- 定义两个指针
left
和right
,分别指向数组的开头和结尾(但是right
指向的是无效的位置,即数组最后一个元素的下一个位置)。 - 进入循环,当
left
小于right
时进行查找。 - 计算中间索引
middle
,采用了防止整数溢出的方式计算,即left + ((right - left) >> 1)
。 - 如果
nums[middle]
大于目标值target
,则更新right
为middle
,因为目标值可能在左半部分,但是middle
不包含在搜索范围内。 - 如果
nums[middle]
小于目标值target
,则更新left
为middle + 1
,因为目标值可能在右半部分。 - 如果
nums[middle]
等于目标值target
,则直接返回middle
,表示找到了目标值的索引。 - 如果循环结束仍未找到目标值,则返回 -1,表示未找到目标值。
这个算法与之前的算法相比,在终止条件和区间的定义上有所不同,但是原理和时间复杂度仍然是相同的,都是 O(log n)。
Given an array of integers nums
which is sorted in ascending order, and an integer target
, write a function to search target
in nums
. If target
exists, then return its index. Otherwise, return -1
.
You must write an algorithm with O(log n)
runtime complexity.
Example 1:
Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4
Example 2:
Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1
Constraints:
1 <= nums.length <= 104
-104 < nums[i], target < 104
- All the integers in
nums
are unique. nums
is sorted in ascending order.
更多内容欢迎关注我(持续更新中,欢迎Star✨)
Github:CodeZeng1998/Java-Developer-Work-Note
技术公众号:CodeZeng1998(纯纯技术文)
生活公众号:好锅(Life is more than code)
博客园: CodeZeng1998
其他平台:CodeZeng1998、好锅
标签:11,二分,right,target,nums,LeetCode704,middle,目标值,left From: https://www.cnblogs.com/codezeng1998/p/18203219