LeetCode 0704. 二分查找

本文主要是介绍LeetCode 0704. 二分查找，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【LetMeFly】704.二分查找

力扣题目链接：https://leetcode.cn/problems/binary-search/

给定一个 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

 

提示：

1. 你可以假设 nums 中的所有元素是不重复的。
2. n 将在 [1, 10000]之间。
3. nums 的每个元素都将在 [-9999, 9999]之间。

方法一：二分查找

二分查找主要有两种写法：对于区间$l$到$r$，采用闭区间还是左闭右开区间。

关于二分查找过程中：

• while (l < r)还是while (l <= r)的关键是：保证while过程中区间不空
• r = mid还是r = mid - 1的关键是：判定过的元素坚决不留在区间内

以C++ lower_bound等左闭右开的二分方法为例：

数组$nums$的有效范围是$[0,n-1]$，则初始值令$l=0,r=n$（左闭右开）。

在循环过程中，保证区间不空，则需要$r>l$（因为如果$l$等于$r$，则因左闭右开区间已经空了）

若$nums[mid]>target$，则$mid$已经被排除了，下次的区间中不应包含$mid$，因此令$r=mid$（右边是开区间，取不到）

while (l < r) {  // [l, r)不空int mid = (l + r) / 2;if (nums[mid] > target) r = mid;  // 新区间[l, mid)if (nums[mid] < target) l = mid + 1;  // 新区间[mid + 1, r)if (nums[mid] == target) return mid;
}

同理，若以闭区间的方法来写：

初始值$l=0,r=n-1$

while (l <= r) {  // [l, r]不空int mid = (l + r) / 2;if (nums[mid] > target) r = mid - 1;  // 新区间[l, mid - 1]if (nums[mid] < target) l = mid + 1;  // 新区间[mid + 1, r]if (nums[mid] == target) return mid;
}

• 时间复杂度$O(\log len(nums))$
• 空间复杂度$O(1)$

AC代码

C++

左闭右开：

class Solution {
public:int search(vector<int>& nums, int target) {int l = 0, r = nums.size();while (l < r) {int mid = (l + r) >> 1;if (nums[mid] > target) {r = mid;}else if (nums[mid] < target) {l = mid + 1;}else {return mid;}}return -1;}
};

闭区间：

class Solution {
public:int search(vector<int>& nums, int target) {int l = 0, r = nums.size() - 1;while (l <= r) {int mid = (l + r) / 2;if (nums[mid] > target) r = mid - 1;if (nums[mid] < target) l = mid + 1;if (nums[mid] == target) return mid;}return -1;}
};

Python

左闭右开：

# from typing import Listclass Solution:def search(self, nums: List[int], target: int) -> int:l, r = 0, len(nums)while l < r:mid = (l + r) // 2if nums[mid] > target:r = midelif nums[mid] < target:l = mid + 1else:return midreturn -1

闭区间：

# from typing import Listclass Solution:def search(self, nums: List[int], target: int) -> int:l, r = 0, len(nums) - 1while l <= r:mid = (l + r) // 2if nums[mid] > target:r = mid - 1elif nums[mid] == target:return midelse:l = mid + 1return -1

同步发文于CSDN，原创不易，转载经作者同意后请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/133610614

这篇关于LeetCode 0704. 二分查找的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---