二分查找

Posted on | In

每次在做二分查找的题目的时候，如果target的值不存在于待查找数组中，边界条件我老写错。

今天来总结下，希望自己能完全攻克这类问题。

该算法的核心思想就是：首先二分查找只能应用在已经有序的数组中，通过每次折半的缩小查找范围直到找到目标元素，若查找范围为1还没找到则说明，待查元素不存在于该有序数组中。

在写二分查找的时候一定要明确查找范围，并且在写代码的过程中始终保持一致。

704. 二分查找

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例 1:

1
2
3
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

示例 2:

1
2
3
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

提示：

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

模板1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int l = 0, r = nums.size() - 1;   // 在[l ... r]的范围里查找target
        while (l <= r){                   // 当l == r时, 区间长度为1, 是有效区间
            int mid = l + (r - l) / 2;    // 取中值
            if (target == nums[mid])  return mid;
            else if (target < nums[mid])
                r = mid - 1;              // target 在[l .... mid - 1]中
            else
                l = mid + 1;              // target 在[mid+1 ... r]中
        }
        return -1;
   }
};

模板2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int l = 0, r = nums.size();     // 在[l ... r) 的范围中查找
        // 由于nums[r]是取不到的[l ... r) 
        // 且l < r是一直成立的 所以while中的语句就是 l < r
        while (l < r){                 
            int mid = l + (r - l) / 2;
            if (target == nums[mid])    return mid;
            else if (target < nums[mid])
                r = mid;                // 查找的范围是[l ... mid)
            else
                l = mid + 1;            // 查找的范围是[mid + 1, r)
        }
        return -1;
    }
};

二分查找衍生出的两个重要函数

STL中二分查找的函数有 3 个(头文件为: #include )：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <algorithm>
namespace std {
  template <class ForwardIterator, class T>
  ForwardIterator lower_bound(ForwardIterator start,
                              ForwardIterator finish,
                              const T& value);

 template <class ForwardIterator, class T, class Compare>
 ForwardIterator lower_bound(ForwardIterator start,
                             ForwardIterator finish,
                             const T& value,
                             Compare comp);
}

namespace std {
  template <class ForwardIterator, class T> 
  ForwardIterator
  upper_bound(ForwardIterator start, ForwardIterator finish,
              const T& value);

  template <class ForwardIterator, class T, class Compare>
  ForwardIterator
  upper_bound(ForwardIterator start, ForwardIterator finish,
              const T& value, Compare comp);
}

lower_bound(起始地址，结束地址，要查找的数值) 返回的是数值 第一个 出现的位置。

功能：函数lower_bound()在first和last中的前闭后开区间进行二分查找，返回大于或等于val的第一个元素位置。如果所有元素都小于val，则返回last的位置.返回的是是一个迭代器,所以要求下标位置的话还需要用返回值减去起始地址.

注意：如果所有元素都小于val，则返回last的位置，且last的位置是越界的！

upper_bound(起始地址，结束地址，要查找的数值) 返回的是 第一个大于待查找数值 出现的位置。

功能：函数upper_bound()返回的在前闭后开区间查找的关键字的上界，返回大于val的第一个元素位置

注意：返回查找元素的最后一个可安插位置，也就是“元素值 > 查找值”的第一个元素的位置。同样，如果val大于数组中全部元素，返回的是last。(注意：数组下标越界)。返回的是是一个迭代器，所以要求下标位置的话还需要用返回值减去起始地址。

binary_search(起始地址，结束地址，要查找的数值) 返回的是是否存在这么一个数，是一个bool值。

lower_bound() 的实现

为了实现方便,我们直接传入一整个数组,并且返回值为下标而不是像STL是迭代器类型.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int lower_bound(vector<int>& nums, int target) {
	if (nums.empty())	return -1;
	int l = 0, r = nums.size(); // [l..r)查找的范围是一个半闭半开的区间
	while (l < r) {
		int mid = l + (r - l) / 2;
		if (nums[mid] == target)	// 往查找的范围需要左移
			r = mid;
		else if (nums[mid] < target)
			l = mid + 1;
		else if (nums[mid] > target)
			r = mid;				// 注意
	}
	return l;
}
upper_bound() 的实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int upper_bound(vector<int>& nums, int target) {
	if (nums.empty())	return -1;
	int l = 0, r = nums.size();		// [l..r) 查找的范围是一个半闭半开的区间
	while (l < r) {
		int mid = l + (r - l) / 2;
		if (nums[mid] == target)
			l = mid + 1;		   // 查找的范围向右移
		else if (nums[mid] < target)
			l = mid + 1;
		else if (nums[mid] > target)
			r = mid;				// 注意
	}
	return l;
}

注意: 二分查找的题目细节是魔鬼，一定要明白自己是在哪个范围里找目标，并且每次在缩小查找范围的时候一定要保证与开始定的范围一样，若开始是全闭区间则缩小了查找范围也一定是全闭区间，若开始是半闭半开区间则缩小了查找范围也一定是半闭半开区间。