代码随想录二刷 ｜ 数组 ｜ 二分查找

题目描述

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]之间。

解题思路 & 代码实现

这道题目的前提是数组为有序数组，同时题目还强调数组中无重复元素，因为一旦有重复元素，使用二分查找法返回的元素下标可能不是唯一的，这些都是使用二分法的前提条件，当看到题目描述满足如上条件的时候，就要想一想是不是可以用二分法了。

写二分法，区间的定义一般为两种，左闭右闭即[left, right]，或者左闭右开即[left, right)。

左闭右闭

第一种写法，定义 target 在一个在左闭右闭的区间里，也就是[left, right]

// 左闭右闭[left, right]
class Solution {
public:
	int search(vector<int> &nums; int target) {
		int left = 0;
		int right = nums.size() - 1; // 定义target在左闭右闭区间
		
		// 左闭右闭，所以用 <= 
		while (left <= right) {
			// 防止溢出，等同于 (left + right) / 2;
			int middle = left + ((right - left) / 2);

			if（nums[middle] > target) { // 如果 nums[middle] > target ，说明target在nums[middle]的左边，在左区间[left, middle - 1]中
				right = middle - 1; // middle已经确定不是target了，因此right需要-1
			} else if (nums[middle] < target) {// 如果 nums[middle] < target ，说明target在nums[middle]的右边，在右区间[middle + 1, right]
				left = middle + 1;	 // middle已经确定不是target了，因此right需要+1
			} else { // nums[middle] = target，找到目标直接返回结果
				return middle;
			}
		}
		// 未找到target返回-1
		return -1;
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

需要注意两点：

• 因为left == right是有意义的，所以while (left <= right) 要使用<=
• 因为当前的nums[middle]一定不是target，那么接下来要查找的左区间结束下标位置就是 middle - 1，所以if (nums[middle] > target) ， right 要赋值为 midddle - 1

时间复杂度：O(log n)
空间复杂度：O(1)

左闭右开

// 左闭右开[left, right)
class Solution {
	int search(vector<int> &nums, int target) {
		int left = 0;
		int right = nums.size(); // 定义target在左闭右开区间
		
		// 左闭右开，所以用 <
		while (left < right) {
			// 防止溢出，等同于 (left + right) / 2;
			int middle = left + ((right - left) >> 1);
			
			if (nums[middle] > target) { // 如果 nums[middle] > target ，说明target在nums[middle]的左边，在左区间[left, middle)中
				right = middle; 
			} else if (nums[middle] < target) { // 如果 nums[middle] < target ，说明target在nums[middle]的右边，在右区间[middle, right)中
				left = middle + 1;
			} else { // nums[middle] = target，找到目标直接返回结果
				return middle;
			}
		}
		// 未找到target返回-1
		return -1;
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

• while (left < right)，这里使用 < ，因为left == right在区间[left, right)是没有意义的
• if (nums[middle] > target)， right 更新为 middle，因为接下来的寻找区间是左闭右开区间[left, middle)，所以right更新为middle，即：下一个查询区间不会去比较nums[middle]

时间复杂度：O(log n)
空间复杂度：O(1)