初阶算法(3):二分法的讲解与实现(C语言),以及二分不止光在有序数组中的应用

这篇具有很好参考价值的文章主要介绍了初阶算法(3):二分法的讲解与实现(C语言),以及二分不止光在有序数组中的应用。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

系列文章目录

 第一章 初阶算法(1):通过简单的排序算法来认识时间复杂度

 第二章 初阶算法(2):进行详细地介绍插入排序的细节和时间复杂度

 第三章 初阶算法(3):二分法的讲解与实现,以及二分不止光在有序数组中的应用


目录

系列文章目录

前言

一、二分法的讲解与实现(C语言)

1.1 为什么在有序数组中用二分法查找?

1.2 二分查找的讲解:

 1.3 二分法的代码实现:

二、二分法的应用(不止在有序数组中)

2.1 常规用法

 2.2 非常规做法(在无需数组中进行)

总结


前言

       哇,转眼就到了第三章,在前两章内(如果想看前两章的内容,请点击系列文章目录的链接),我们主要讲解了时间复杂度为O(N^2)的排序算法冒泡排序选择排序插入排序),不知道大家看的如何?

       在这一章,我们主要讲述二分法的使用,讲述有关二分法的三道编程题来打破大家对二分法只能用在有序数组的思想


一、二分法的讲解与实现(C语言)


1.1 为什么在有序数组中用二分法查找?


       一般地,我们在一个有序数组中查找一个数字,如果我们一一查找是要根据数据量的,有时会很快,有时会很慢!这就比较麻烦,所以我们不能用一一查找。

       为什么说有时很快,有时很慢呢?假如,我们现在有一个有序数组(1,2,3,4,5,6,7,8,9,10,11,12,13),如果你要查找1的话, 一一查找只需遍历一位即可;但如果你要查找13的话,则需要将整个数组遍历完

       此时,这个要查找的数组是一个有序数组,我们就可以利用有序数组的特性去使用二分查找去寻找我们所要查找的数字。


1.2 二分查找的讲解:


       在上面的引子中说在一个有序数组中使用二分查找,那么二分查找是如何实现的呢?

 二分查找的基本思路是:先找到中间的数与要查找数进行比较,然后分情况

       1)如果比要查找数小,那么就舍弃左边一半的数,在右边一半的数再找到中间的数与要查找数进行比较重复此过程

       2)如果比要查找数大,那么就舍弃右边一半的数,在左边一半的数再找到中间的数与要查找数进行比较重复此过程

       最后直到查找到最后一个数

       接下来,进行估算二分查找的时间复杂度,用最坏的数据进行计算,因为一次代码流程要舍弃一半的数,所以时间复杂度为O(logN)


 1.3 二分法的代码实现:


       经过上面的详细分析后,小编觉得各位看官已经充分了解了二分法的思路了,那么接下来,和小编进行二分法的实现吧!

实现二分法的代码如下:

    int left = 0;
    int right = n - 1;
    while (left <= (right - 1)){     //判断条件是左边指向的位置大于右边指向的位置
        int mid = (left + right) / 2;//中点的位置要随时更新,以便求出最新的中点坐标
        if(k > arr[n - 1])      //如果要查找的数大于数组的最后一个数时,则不需要继续查找
            break;
        if (arr[mid] == k){
            right = mid;
            if(arr[mid - 1] < arr[mid])  //与中间数进行比较
                ans = mid;
        }
        if(arr[mid] > k)     //随时更新中点坐标
            right = mid;  
        if(arr[mid] < k)
            left = mid;
    }

二、二分法的应用(不止在有序数组中)


2.1 常规用法


       在上面我们已经进行过在一个有序数组中查找某一个数,接下来,我们将写出一个变式:查找某个位置。 

题目:你需要输入一个n,一个数k,然后输入一个长度为n个大小的数组arr,然后你需要在arr上找满足>=K的最左位置,并且输出这个位置,如果不存在这个位置就输出-1。

      看到这道题面,小编我的第一个反应是将这个有序数组进行遍历, 只要找到第一个数字等于k,则是我们所要查找的位置,那么这种方法就和上面小编写的第一道体题的思想一样就是有时很慢。有时很快

       这篇文章中,我们学习了二分法,就要利用二分法进行解题。基本思路是:先找到中间的数与要查找数进行比较,然后分情况

       1)如果比要查找数小,>=K的最左位置应该在右边,那么就舍弃左边一半的数,在右边一半的数再找到中间的数与要查找数进行比较重复此过程

       2)如果比要查找数等于或大于,>=K的最左位置应该在右边,那么就舍弃右边一半的数,如果等于k的话进行标记,在左边一半的数再找到中间的数与要查找数进行比较重复此过程最后将整个数组进行遍历,找到第一个标记的数字

       最后直到查找到最后>=K一个数

实现题目的代码如下:

int main()
{
	int n = 0, k = 0;
	scanf("%d %d", &n, &k);
	int a[1000000];
	for (int i = 0; i < n; i++)
		scanf("%d", &a[i]);
	int left = 0;
	int right = n - 1;
	int mid = 0;
	int reslut = -1;    //因为如果找不到,就输出-1
	while (left <= right){
		mid = (left + right) / 2;
		if (a[mid] >= k){
			reslut = mid;
			right = mid - 1;
		}
		else
			left = mid + 1;
	}
	printf("%d\n", reslut);
	return 0;
}

 2.2 非常规做法(在无需数组中进行)


       二分法真的只能用在有序数组中吗?小编在了解完这个题目后,也是大吃一惊!答案是可以的!

       接下来,跟随小编的步伐进行学习吧!看这道题目:局部最小值问题

局部最小的概念:1)数组中0位置的数比1位置的数要

                             2)数组中N-1位置的数比N-2位置的数要

                             3)数组中第i位置的数要比两边位置的数都要

题目: 给定无序数组arr,已知arr中任意两个相邻的数都不相等,只需要返回arr中任意一个局部最小出现的位置即可,如果不存在这个位置就输出-1。

       小编进行分析可得:

       先判断0位置的数和1位置的数,再判断N-1位置的数和N-2位置的数。如果这两种情况都不成立,那么一定会出现一开始是下降的,在最后是上扬的又因为数组中每两个数都不相同,所以在1到N-2中一定有局部最小

       接下来,我们就可以利用二分进行舍弃数字。找到中间位置的数与两边位置的数进行比较,如果都小于,则返回中间位置的数;如果有一边不小于,则舍弃一半,在另一半继续寻找。

实现题目的代码如下:

int main() {
    int n = 0;
    scanf("%d", &n);
    int a[100000];
    for (int i = 0; i < n; i++) {
        scanf("%d", a + i);
    }
    int left = 0;
    int right = n - 1;
    int mid = -1;
    if (n == 1 || a[0] < a[1]) {
        printf("%d\n", 0);
        return 0;
    }
    else if (a[n - 1] < a[n - 2]) {
        printf("%d\n", n - 1);
        return 0;
    } else {
        while (left <= right) {
            mid = (left + right) / 2;

            if (a[mid] > a[mid - 1]) {
                right = mid - 1;
            }
            else if (a[mid] > a[mid + 1]) {
                left = mid + 1;
            } else {
                //flag = 1;
                printf("%d\n", mid);
                return 0;
            }
        }
    }
    return 0;
}

总结

       以上就是今天要讲的内容,本文介绍了二分法及其在无序数组中的应用,过几天小编会进行编写关于二分法的一些习题,希望大家看完以后,进行点评,谢谢大家!文章来源地址https://www.toymoban.com/news/detail-626229.html

到了这里,关于初阶算法(3):二分法的讲解与实现(C语言),以及二分不止光在有序数组中的应用的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构和算法之二分法查找

    二分法查找,也称作 二分查找 或 折半查找 ,是一种在有序数组中快速查找特定元素的算法。它采用分治法思想,通过将问题划分为规模更小的子问题,并且通过对子问题的查找来解决原问题。 二分法查找的思路是不断地将数组一分为二,然后判断目标值在哪一部分,进而

    2024年02月09日
    浏览(45)
  • 算法刷题营【Day1】:: 704.二分查找:二分法详谈与相关刷题

    本内容是笔者结合《代码随想录》总结所得,记录学习过程,分享知识! 目录: 1. 开篇例题:704. 二分查找 2. 题解参考(模板写法) - - 2.1 方法一:左闭右闭写法 - - 2.2 方法二:左闭右开写法 3. 模板解释:左闭右闭 - - 3.1 区间划定 - - 3.2 left 、right 移动问题 - - 3.3 循环条件

    2024年02月04日
    浏览(45)
  • 【数值分析】非线性方程求根,二分法,割线法,matlab实现

    收敛阶 lim ⁡ k → ∞ ∣ e k + 1 ∣ ∣ e k ∣ r = C 0    ,    r 为收敛阶 lim_{ktoinfty} frac{|e_{k+1}|}{|e_k|}^r=C0 ,,,,, r为收敛阶 k → ∞ lim ​ ∣ e k ​ ∣ ∣ e k + 1 ​ ∣ ​ r = C 0 , r 为收敛阶 二分法是线性收敛的,如果指定精度 ϵ { epsilon } ϵ ,则最多需要迭代步数 k = ⌈ log ⁡

    2024年01月22日
    浏览(75)
  • 276.【华为OD机试】矩阵匹配(二分法—Java&Python&C++&JS实现)

    🚀点击这里可直接跳转到本专栏,可查阅顶置最新的华为OD机试宝典~ 本专栏所有题目均包含优质解题思路,高质量解题代码(JavaPythonC++JS分别实现),详细代码讲解,助你深入学习,深度掌握!

    2024年04月29日
    浏览(45)
  • 初探二分法

    智能化校园:深入探讨云端管理系统设计与实现(一) 智能化校园:深入探讨云端管理系统设计与实现(二) 题目:给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。 提示: 你可以

    2024年01月25日
    浏览(57)
  • 二分法MATLAB代码

    本质是通过不断进行区间压缩来获取函数零点。 二分法的终止条件:区间长度小于等于精度要求 。 流程: 如下图所示:

    2024年02月05日
    浏览(46)
  • 二分法相关使用

    在线OJ:704. 二分查找 有序数组下的二分思路如下: 由于这里是有序数组, 我们可以可以先得到中点位置, 中点可以把数组分为左右两边; 如果中点位置的值等于目标值, 直接返回中点位置; 如果中点位置的值小于目标值, 则去数组中点左侧按同样的方式查找; 如果中点位置的值大

    2024年02月07日
    浏览(43)
  • 二分法简单题

    2024年01月24日
    浏览(52)
  • 【二分查找】一文带你掌握二分法 (附万能模板)

    一、简介 哪怕没有学过编程的同学,也许不知道二分法这个名字,但也一定接触过它的核心思想。不了解的同学也没关系,我用一句话就能概括出它的精髓: 将一个区间一分为二,每次都舍弃其中的一部分。 二分法能够极大地降低我们在解决问题时的时间复杂度。假如你要

    2024年01月19日
    浏览(54)
  • 【剑指Offer】二分法例题

    链表是数据结构中重要的一个章节,他的重要性也不言而喻,在未来不管是笔试还是面试都会遇到这类的题目,所以接下来我就会把一些链表的常考的题目全部整理出来供大家学习指正。 题目链接 描述: 给定一个长度为n的数组nums,请你找到峰值并返回其索引。数组可能包

    2023年04月13日
    浏览(44)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包