设为“置顶或星标”,第一时间送达干货。
![二分查找就该这样学 二分查找就该这样学](https://cxyxiaowu-1257126549.cos.ap-guangzhou.myqcloud.com/2020/05/1590745298-bb343e582a53075.jpeg)
转自景禹
小禹禹,你们好呀!从今天开始景禹就要开始给大家分享查找和排序算法,有没有很鸡冻。查找算法在日常的考试、面试中都极为常见。
基础
静态查找(Static Search):数据集合稳定,不需要添加,删除元素的查找操作。
动态查找(Dynamic Search):在数据集合中进行查找的过程中,需要同时添加或删除元素的查找操作。
关键字(key):数据元素(或记录)中某个数据项的值,用它可以唯一的标识(识别)一个数据元素(或记录)。
对于静态查找来说,我们可以采用用线性表结构组织数据,这样可以使用顺序查找算法,如果我们再对关键字进行排序,则可以使用折半查找算法或斐波那契查找算法等来提高查找的效率。
对于动态查找来说,我们则可以考虑使用二叉排序树的查找技术,另外我们还可以使用散列表结构来解决一些查找问题,这些查找算法景禹都会一点儿一点儿介绍给小禹禹的。
其实本质上查找算法一般分为两类:
-
顺序查找(Sequential Search):将顺序遍历链表或数组,并检查每个元素。(比如线性查找) -
区间查找(Interval Search):这类算法是专门为查找排序的数据结构而设计的。这些类型的查找算法比线性查找有效得多,因为它们反复检查查找空间的中心并不断将查找空间缩减。(比如二分查找)
景禹今天主要给小禹禹分享一下线性查找和二分查找,其中线性查找的的思想简单,景禹就不一步一步给大家分析演示了,不过提供了动画演示,不理解的小禹禹可以对照着看一下。
线性查找
顺序查找(Sequential Search)又叫线性查找(Linear Search),是最基本的查找技术,它的查找过程为:从表中的第一个(或者最后一个)记录开始,逐个进行记录的关键字和给定值的比较,若某个记录的关键字和给定值比较相等,则查找成功。如果查找了所有的记录仍然找不到与给定值相等的关键字,则查找不成功。
动画演示
实现代码
从前往后进行遍历查找:
#include <stdio.h>
int search(int arr[], int n, int x)
{
int i;
for (i = 0; i < n; i++)
if (arr[i] == x)
return i;
return -1;
}
int main(void)
{
int arr[] = { 5, 13, 19, 21, 37, 56, 64, 75, 80, 88, 92 };
int x = 64;
int n = sizeof(arr) / sizeof(arr[0]);
int result = search(arr, n, x);
(result == -1) ? printf("Element is not present in array")
: printf("Element is present at index %d",
result);
return 0;
}
从后往前进行遍历查找:
int search(int arr[], int n, int x)
{
int i = n-1;
while(arr[i] != x){
i--;
}
if(i >= 0)
return i;
return -1;
}
时间复杂度
线性查找的时间复杂度为
二分查找
二分查找又叫做折半查找,其查找过程为:先确定待查记录所在的范围(区间),然后逐步缩小范围知道找到或者找不到该记录为止。注意二分查找是在有序表上进行的,且二分查找也是分治思想的很好例证。之前景禹在谈递归与分治时就曾介绍过二分查找,今日再详细探讨一下。
我们以上面的有序数组,查找关键字21的数据元素为例进行说明。
第一步:设置一个指向有序数组第一个元素 5 的low指针,和一个指向有序数组的最后一个元素 92 的high指针。
![二分查找就该这样学 二分查找就该这样学](https://cxyxiaowu-1257126549.cos.ap-guangzhou.myqcloud.com/2020/05/1590745298-5e998474a8ea694.png)
第三步:将给定值21与mid指针指向的值56进行比较,21 < 56,说明待查找元素21若存在,必在区间 [low,mid-1] 的范围内,则令 high = mid - 1 = 5- 1 = 4.
第四步:重新计算 mid 的值,mid =⌊(0+4)/2⌋=2.
第五步:将给定值21与mid指向的值19进行比较,21 > 19,说明待查找元素21若存在,必在区间 [mid+1,high] 的范围内,则令 low = mid + 1 = 2+ 1 = 3.
第六步:重新计算mid 的值,mid =⌊(3+4)/2⌋=3.
第七步:将给定值21与mid指向的值21进行比较,发现相等,查找成功。
从上面的例子可见,折半查找过程以处于区间中间位置mid记录的值和给定值比较,若相等,则查找成功,若不相等,则缩小范围,直至新的区间中间位置mid记录的值等于给定值或者查找区间的大小小于零时(表示查找不成功)为止。
二分查找递归实现
#include <stdio.h>
int binarySearch(int arr[], int low, int high, int x)
{
if (high >= low) {
int mid = low + (high - low) / 2;
//判断mid指向值是否等于指定值x
if (arr[mid] == x)
return mid;
//如果mid指向的元素的值大于指定值x,
//则递归地遍历区间[l,mid-1]
if (arr[mid] > x)
return binarySearch(arr, low, mid - 1, x);
//如果mid指向的元素的值小于指定值x,
//则递归地遍历区间[mid+1, high]
return binarySearch(arr, mid + 1, high, x);
}
//查找的元素不存在返回-1
return -1;
}
int main(void)
{
int arr[] = { 5, 13, 19, 21, 37, 56, 64, 75, 80, 88, 92 };
int n = sizeof(arr) / sizeof(arr[0]);
int x = 64;
int result = binarySearch(arr, 0, n - 1, x);
(result == -1) ? printf("Element is not present in array")
: printf("Element is present at index %d",
result);
return 0;
}
二分查找迭代实现
int binarySearch(int arr[], int low, int high, int x)
{
while(low <= high){
int mid = low + (high - low) / 2;
if (arr[mid] == x)
return mid;
if (arr[mid] < x){
low = mid + 1;
}
else{
high = mid - 1;
}
}
return -1;
}
时间复杂度
为了清晰地计算二分查找的时间复杂度,我们将例子中的数组转化为一颗二叉树。
查找21仅需要比较2次,查找37仅需要比较3次。显而易见,对于一个有序数组而言,查找某个元素的判断次数最多也就是上面的一颗判断树的深度,而具有n个结点的判定树的深度为 ,所以在一个有序数组中查找一个元素的时间复杂度为 级别。
二分查找的应用
LeetCode 704. 二分查找 (Binary Search)
小禹禹赶紧去力扣提交一下,体验一波成功感吧,哈哈!!!景禹为了让小禹禹对二分查找理解更深刻,我们再来看一道题目。
题目描述
统计一个数字在排序数组中出现的次数。
例如输入排序数组[1, 2, 3, 3, 3, 3, 4, 5]和数字3,由于3在这个数组中出现了4次,因此输出4。
示例
示例 1:
输入:[1, 2, 3, 3, 3, 3, 4, 5] , 3
输出:4 解释:数组中总共有4个3
题解:
第一种方式当然特别简单,只需要写一个循环,遍历数组一遍,统计出排序数组中重复数字的个数。时间复杂度为 .
另一种方式就是我们今天所学习的二分查找了,怎么办?
小禹禹:嗯???还可以用二分查找,也就意味着时间复杂度降到 .
景禹:的确如此,那就让我们快乐的开始吧。
首先我们应该注意到输入的是一个 排序数组 ,面试只要提到有序数组这种,小禹禹一定要有警惕性,面试官可不想只看到 的解法。
二分查找本身是用于查找数组中是否存在一个元素,若存在在返回数组的下标,若不存在,则返回-1。而现在我们我们要统计的是数组中重复元素出现的次数,有没有可能对二分查找进行修改后做到呢?答案是肯定的。
我们只需要确定出第一个3的位置以及最后一个3的位置,然后将两个位置相减并加一,就是重复元素的个数。
如何计算第一个重复元素的位置?
第一步:依然是设置一个指向第一个元素的low指针,和指向最后一个元素的high指针
第二步:计算指针 mid =⌊(0+7)/2⌋=3.
第三步:比较mid 指向的元素 3 与重复元素的大小,如果 mid 指向的元素 大于等于 重复元素,则令
high = mid - 1
. 否则,令 low = mid + 1
. 这里是是大于等于,故 high = 3 - 1 = 2
.
第四步:计算指针 mid =⌊(0+2)/2⌋=1.
第五步:比较mid 指向的元素 2 与重复元素 3 的大小, 2 < 3,则 low = mid + 1 = 2
第六步:计算 mid =⌊(2+2)/2⌋=2.
第七步:比较mid 指向的元素 3 与重复元素 3 的大小, 3 <= 3,则 high = mid - 1 = 1
此时 low > high
,退出循环并返回指针 low 的值 2。
如何获得最后一个重复元素的位置?
与上面寻找第一个重复元素的位置一样,我们只需要将判断条件进行更改,也就是说,当mid指向的值 小于等于 重复元素,则 low = mid + 1
,否则,令 high = mid - 1
.
通俗来讲,我们寻找第一个重复元素,将high指针向low 靠近,寻找最后一个元素,将low指针向high靠近。
我们一起来看代码吧!超级简单。
计算第一个重复元素的位置:
int binarySearch_start(int arr[], int low, int high, int x)
{
while(low <= high){
int mid = low + (high - low) / 2;
if (arr[mid] < x){
low = mid + 1;
}
else{
high = mid - 1;
}
}
return low;
}
计算最后一个重复元素的位置:
int binarySearch_end(int arr[], int low, int high, int x)
{
while(low <= high){
int mid = low + (high - low) / 2;
if (arr[mid] <= x){
low = mid + 1;
}
else{
high = mid - 1;
}
}
return low;
}
至于重复元素的个数则为:最后一个重复元素的位置 – 最后一个重复元素的位置 + 1.
当然我们可以有一种更简洁的思路,那就是找到第一个元素的位置,然后找出最后一个元素的位置的下一个位置,然后进行相减即可得到重复元素的个数:
#include <stdio.h>
int binarySearch(int arr[], int low, int high, int x)
{
while(low <= high){
int mid = low + (high - low) / 2;
if (arr[mid] < x){
low = mid + 1;
}
else{
high = mid - 1;
}
}
return low;
}
int main(void)
{
int arr[] = { 1,2,3,4,4,4,4,4,4,4,6,6,7,8,9,10 };
int n = sizeof(arr) / sizeof(arr[0]);
int x = 4;
int start = binarySearch(arr, 0, n - 1, x);
int end = binarySearch(arr, 0, n -1 ,x+1);
int result = end - start;
printf("The number of Repeating element is %d",result);
return 0;
}
景禹今天就写到这里啦,希望小禹禹有所收获,一切顺利,学习愉快,原创不易,素质三连是对景禹的最大鼓励!一起加油呀~~
推荐阅读
• C++是如何从代码到游戏的?• 告诉你一个学习编程的诀窍(建议收藏)• 自学编程的八大误区!克服它!• 新手如何有效的刷算法题(LeetCode)• 10款VS Code插件神器,第7款超级实用!• 在拼多多上班,是一种什么样的体验?我tm心态崩了呀!• 写给小白,从零开始拥有一个酷炫上线的网站!
欢迎关注我的公众号“五分钟学算法”,如果喜欢,麻烦点一下“在看”~
![二分查找就该这样学 二分查找就该这样学](https://cxyxiaowu-1257126549.cos.ap-guangzhou.myqcloud.com/2020/05/1590745302-1a765c637dfe1c2.jpeg)
原文始发于微信公众号(五分钟学算法):二分查找就该这样学