Leetcode 704 二分查找()-其他

Leetcode 704 二分查找()

题目描述：

给定一个 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]之间。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/binary-search
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

问题分析：
首先取数组中间元素的位置，不难写出int mid = (left + right) / 2;，这么写其实有一个问题，就是数值越界，例如left和right都是最大int，这么操作就越界了，在二分法(opens new window)中尤其需要注意！
所以可以这么写：int mid = left + ((right – left) / 2);
需要有这个意识！
https://leetcode.cn/problems/binary-search/solution/er-fen-cha-zhao-by-leetcode-solution-f0xw/
官方题解

// 版本一 target 是在一个在左闭右闭的区间里，也就是[left, right]

class Solution {public:
int search(vector& nums, int target) {
int left = 0;
int right = nums.size() – 1; // 定义target在左闭右闭的区间里，[left, right]
while (left <= right)
{ // 当left==right，区间[left, right]依然有效，所以用 <=
int middle = left + ((right – left) / 2); // 防止溢出 等同于(left + right)/2
if (nums[middle] > target)
{ right = middle – 1; // target 在左区间，所以[left, iddle – 1]
}
else if (nums[middle] < target)
{ left = middle + 1; // target 在右区间，所以[middle + 1, right]
} else { // nums[middle] == target
return middle; // 数组中找到目标值，直接返回下标
}
}
// 未找到目标值
return -1;
}};

<br>
当需要在一个有序数组中查找一个特定值时，二分查找算法是一种高效的解决方案。它通过将目标值与数组中间元素进行比较来确定目标值所在的区间，并将搜索范围缩小到数组的一半，以便在更短的时间内找到目标值。
这个算法的实现包含三个主要步骤：

1.初始化搜索范围：将搜索范围定义为整个数组，即[left, right]。在本例中，left被初始化为0，right被初始化为nums数组的最后一个索引。


2.不断缩小搜索范围：在while循环中，通过比较中间元素与目标值的大小，可以确定目标值所在的区间。如果中间元素比目标值大，则目标值必定在左侧区间，因此将搜索范围缩小到左侧区间；如果中间元素比目标值小，则目标值必定在右侧区间，因此将搜索范围缩小到右侧区间。如果中间元素等于目标值，则找到了目标值，直接返回该元素的下标。


3.搜索完成：如果while循环完成时仍未找到目标值，则表示目标值不在数组中，返回-1。

4.需要注意的是，在计算中间元素时，要使用(left + (right - left) / 2)而不是(left + right) / 2，以防止整数溢出的问题。另外，循环条件中使用了left <= right而不是left < right，是因为当搜索范围缩小到只剩下一个元素时，该元素仍可能是目标值，因此需要将搜索范围限定为[left, left]或[right, right]。



<h3>描述一下其中left right充当的角色和功能 </h3>
在二分查找算法中，left和right变量用来表示当前搜索范围的左右边界。具体来说，它们的功能如下：

left表示当前搜索范围的左边界，初始值为0，也就是数组的第一个元素的下标。

right表示当前搜索范围的右边界，初始值为nums.size() - 1，也就是数组的最后一个元素的下标。

在算法执行过程中，left和right的值会根据当前中间元素与目标值的大小关系，不断缩小搜索范围，以便在更短的时间内找到目标值。

当left和right相等时，搜索范围缩小到了只有一个元素，此时需要根据这个元素是否等于目标值来决定是否找到目标值。

总之，left和right的角色是表示当前搜索范围的左右边界，它们的值会随着搜索过程的进行而不断变化，以缩小搜索范围。在搜索过程结束后，left和right所表示的搜索范围可能变成了只有一个元素，此时需要根据这个元素是否等于目标值来确定算法的返回值。

题目描述：

给定一个 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]之间。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/binary-search
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

问题分析：
首先取数组中间元素的位置，不难写出int mid = (left + right) / 2;，这么写其实有一个问题，就是数值越界，例如left和right都是最大int，这么操作就越界了，在二分法(opens new window)中尤其需要注意！
所以可以这么写：int mid = left + ((right – left) / 2);
需要有这个意识！
https://leetcode.cn/problems/binary-search/solution/er-fen-cha-zhao-by-leetcode-solution-f0xw/
官方题解

// 版本一 target 是在一个在左闭右闭的区间里，也就是[left, right]

class Solution {public:
int search(vector& nums, int target) {
int left = 0;
int right = nums.size() – 1; // 定义target在左闭右闭的区间里，[left, right]
while (left <= right)
{ // 当left==right，区间[left, right]依然有效，所以用 <=
int middle = left + ((right – left) / 2); // 防止溢出 等同于(left + right)/2
if (nums[middle] > target)
{ right = middle – 1; // target 在左区间，所以[left, iddle – 1]
}
else if (nums[middle] < target)
{ left = middle + 1; // target 在右区间，所以[middle + 1, right]
} else { // nums[middle] == target
return middle; // 数组中找到目标值，直接返回下标
}
}
// 未找到目标值
return -1;
}};

<br>
当需要在一个有序数组中查找一个特定值时，二分查找算法是一种高效的解决方案。它通过将目标值与数组中间元素进行比较来确定目标值所在的区间，并将搜索范围缩小到数组的一半，以便在更短的时间内找到目标值。
这个算法的实现包含三个主要步骤：

1.初始化搜索范围：将搜索范围定义为整个数组，即[left, right]。在本例中，left被初始化为0，right被初始化为nums数组的最后一个索引。


2.不断缩小搜索范围：在while循环中，通过比较中间元素与目标值的大小，可以确定目标值所在的区间。如果中间元素比目标值大，则目标值必定在左侧区间，因此将搜索范围缩小到左侧区间；如果中间元素比目标值小，则目标值必定在右侧区间，因此将搜索范围缩小到右侧区间。如果中间元素等于目标值，则找到了目标值，直接返回该元素的下标。


3.搜索完成：如果while循环完成时仍未找到目标值，则表示目标值不在数组中，返回-1。

4.需要注意的是，在计算中间元素时，要使用(left + (right - left) / 2)而不是(left + right) / 2，以防止整数溢出的问题。另外，循环条件中使用了left <= right而不是left < right，是因为当搜索范围缩小到只剩下一个元素时，该元素仍可能是目标值，因此需要将搜索范围限定为[left, left]或[right, right]。



<h3>描述一下其中left right充当的角色和功能 </h3>
在二分查找算法中，left和right变量用来表示当前搜索范围的左右边界。具体来说，它们的功能如下：

left表示当前搜索范围的左边界，初始值为0，也就是数组的第一个元素的下标。

right表示当前搜索范围的右边界，初始值为nums.size() - 1，也就是数组的最后一个元素的下标。

在算法执行过程中，left和right的值会根据当前中间元素与目标值的大小关系，不断缩小搜索范围，以便在更短的时间内找到目标值。

当left和right相等时，搜索范围缩小到了只有一个元素，此时需要根据这个元素是否等于目标值来决定是否找到目标值。

总之，left和right的角色是表示当前搜索范围的左右边界，它们的值会随着搜索过程的进行而不断变化，以缩小搜索范围。在搜索过程结束后，left和right所表示的搜索范围可能变成了只有一个元素，此时需要根据这个元素是否等于目标值来确定算法的返回值。