学习笔记之二分查找

什么是二分查找

二分查找

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

二分查找的思路是:

  • 如果目标值等于中间元素,则找到目标值。
  • 如果目标值较小,继续在左侧搜索。
  • 如果目标值较大,则继续在右侧搜索。

我们的题目条件是升序数组,也就是说,数组已经进行了排序。那么我们先寻找数组最中间的值mid,我们首先去对比中间值的大小,如果$target>mid$,那么我们就去搜索从mid分开的数组右侧,否则就去搜索数组左侧。

二分查找的非递归代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int BinarySearch(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target)
return mid;
if (target < nums[mid])
right = mid - 1;
else
left = mid + 1;
}
return -1;
}

二分查找的优势

二分查找的时间复杂度为$O(log_2n)$,相比于遍历的时间复杂度$O(n)$,明显就快了很多。

二分查找的边界问题

在 ${1,2,3,3,3,4,5}$ 这个例子中,我们的目标值如果为3,那么二分查找到的数组下标为3,也就是最中间那个数。那如果我想返回最先出现的下标,也就是下标2,或者最后出现的下标,比如下标4,那么我们需要收缩查找。

搜索左侧边界

我们在搜索的时候,想要返回左侧边界,则需要收缩右侧的搜索范围,即当我们遇到 $nums[mid] == target$ 时,不要马上返回结果,而是继续收缩查找区间,将右侧的区间缩小,使得 $right = mid-1$ ,此时我们再次判断 $left <= right$ 条件进入循环判断,如果$left == right$,那么 $mid == left$ ,即搜索左侧;如果 $left <= right$ ,$right$收缩区间,直到 $mid == left$。

如果一直没有搜索到 $target$,有两种情况:

  • $target$ 比数组里所有的数都大,此时 $l = mid +1$ 不断执行,那么最后会出现 $l == n$ 的情况,此时我们应该返回-1
  • $target$ 比数组里所有的数都小,此时 $r = mid -1$ 不断执行,那么最后会出现 $r == -1$ 的情况,但是由于我们是判断左侧区间,也就是说 ①$target$的下标是0,$nums[mid] == target$ 执行$r = mid - 1$;②$target$比所有元素都小,$nums[mid] > target$ 执行$r = mid - 1$;此时如果单纯判断$r == -1$,则无法分辨①和②两种情况,因此我们需要用 $nums[l] != target$ 判断。

非递归代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int LeftBinarySearch(int[] nums, int target) {
int n = nums.length;
int l = 0;
int r = n - 1;
while (l <= r) {
int mid = (l + r) / 2;
if (nums[mid] == target)
r = mid - 1;
else if (nums[mid] > target)
r = mid - 1;
else if (nums[mid] < target)
l = mid + 1;
}
if (l > n - 1 || (nums[l] != target))
return -1;
return l;
}

搜索右侧边界

与左侧搜索同理,我们需要收缩左侧的搜索范围。我们只需要对上面的代码进行一些微调就可以了。

如果一直没有搜索到 $target$,有两种情况:

  • $target$ 比数组里所有的数都大,此时 $l = mid +1$ 不断执行,那么最后会出现 $l == n$ 的情况,但是由于我们是判断右侧区间,也就是说 ①$target$的下标是$n-1$,$nums[mid] == target$ 执行$l = mid + 1$;②$target$比所有元素都小,$nums[mid] > target$ 执行$l = mid + 1$;此时如果单纯判断$r == n$,则无法分辨①和②两种情况,因此我们需要用 $nums[r] != target$ 判断。
  • $target$ 比数组里所有的数都小,此时 $r = mid -1$ 不断执行,那么最后会出现 $r == -1$ 的情况,此时我们应该返回-1。

非递归代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int RightBinarySearch(int[] nums, int target) {
int n = nums.length;
int l = 0;
int r = n - 1;
while (l <= r) {
int mid = (l + r) / 2;
if (nums[mid] == target)
l = mid + 1;
else if (nums[mid] > target)
r = mid - 1;
else if (nums[mid] < target)
l = mid + 1;
}
if (r < 0 || (nums[r] != target))
return -1;
return r;
}

二分查找题目

未完

文章目录
  1. 1. 什么是二分查找
    1. 1.1. 二分查找
    2. 1.2. 二分查找的优势
  2. 2. 二分查找的边界问题
    1. 2.1. 搜索左侧边界
    2. 2.2. 搜索右侧边界
  3. 3. 二分查找题目
|