查看原文
其他

二分查找就该这样学

景禹 景禹 2022-06-09

小禹禹,你们好呀!从今天开始景禹就要开始给大家分享查找和排序算法,有没有很鸡冻。查找算法在日常的考试、面试中都极为常见。

基础

静态查找(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指针。

第二步:计算 low 指针与 high 指针的中点,并用 mid 指针保存。low 的初值为0, high 的初值为10,则 ,即指向记录56.

第三步:将给定值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;
}


景禹今天就写到这里啦,希望小禹禹有所收获,一切顺利,学习愉快,原创不易,素质三连是对景禹的最大鼓励!一起加油呀~~

作者:景禹,一个追求极致的共享主义者,想带你一起拥有更美好的生活,化作你的一把伞。


您可能也对以下帖子感兴趣

文章有问题?点此查看未经处理的缓存