二分查找(C语言实现)

这篇具有很好参考价值的文章主要介绍了二分查找(C语言实现)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

二分查找的前提:

一个整形有序数组中查找具体某个数

以下以数组元素为偶数个做例

  二分查找(折半查找)的思想:对于已按关键字排序的序列,经过一次比较,可将序列分割成两部分,然后只在有可能包含待查元素的一部分中继续查找,并根据试探结果继续分割,逐步缩小查找范围,直至找到或找不到为止。

 下图为程序在数组中寻找整数6的过程 

进入循环之前,先定义数组的左右下标:左下标为0,右下标为数组元素个数减去1

二分查找(C语言实现)

  while (left <= right),当作下标小于右下标时,进入循环

第一次循环:

二分查找(C语言实现)

if 和else  if语句内均没有break 语句,所以循环继续

第二次循环:

二分查找(C语言实现) 第三次循环:

 二分查找(C语言实现)

跳出循环后判断right的关系,这个if语句是在没有找到的情况下进入 

 代码如下:文章来源地址https://www.toymoban.com/news/detail-507041.html

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
int main()
{
    int arr[10] = { 1,2,3,4,5,6,7,8,9,10 };//已知的整形有序数组
    int x = 0;//x是要寻找的数
    int left = 0;//左下标
    int right = sizeof(arr) / sizeof(arr[0]) - 1;//数组右下标  
    scanf("%d", &x);
    while (left <= right)
    {
        int mid = left+(right-left)/2;//找到最中间的数
        if (x < arr[mid])
        {
            right = mid-1;
        }
        else if (x > arr[mid])
        {
            left = mid+1;
        }
        else
        {
            printf("找到了,下标是%d\n", mid);
            break;
        }
    }
    if (right < left)
    {
        printf("没找到");
    }

    return 0;
}

除了给定整形有序数组外,我们还可以自己输入一个有序数组和需要查找的数
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
int main()
{
    int arr[100];
    int j = 0;//j为需要寻找的数
    int i = 0;
    int left = 0;
    int right = 0;
    while (1)
    {
        scanf("%d", &arr[i]);
        i++;
        if (getchar() == '\n')
        {
            break;//遇到回车则证明数组输入结束
        }
    }
    scanf("%d", &j);
    right = i - 1;//总共输入了i个元素,最大下标为i-1
    while (left <= right)
    {
        int mid = left + (right - left) / 2;
        if (j < arr[mid])
        {
            right = mid - 1;
        }
        else if (j > arr[mid])
        {
            left = mid + 1;
        }
        else
        {
            printf("找到了,下标为%d\n", mid);
            break;
        }

    }
    //左右下标发生交叉的情况,则证明没有找到
    if (left > right)
    {
        printf("没找到\n");
    }
    return 0;
}

到了这里,关于二分查找(C语言实现)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 34. 在排序数组中查找元素的第一个和最后一个位置(二分查找)

    二分查找到目标值然后左右找到坐标 问题在于:找左右坐标的时候时间复杂度不是 O(logN) 之前提到过二分查找不仅可找到相等的数值,更关键的是 它可以将数组分为截然不同的两种情况 ,因此我们可以借助这个性质找到 第一个大于等于 target 的值(左下标) 和 第一个大于

    2024年01月22日
    浏览(49)
  • 二分查找实例1(在排序数组中查找元素的第一个和最后一个位置)

    给你一个按照非递减顺序排列的整数数组  nums ,和一个目标值  target 。请你找出给定目标值在数组中的开始位置和结束位置。 如果数组中不存在目标值  target ,返回  [-1, -1] 。 你必须设计并实现时间复杂度为  O(log n)  的算法解决此问题。 示例 1: 示例 2: 示例 3: 提示

    2024年02月09日
    浏览(44)
  • 【C语言】二分查找(详解)

    🎥 岁月失语唯石能言的个人主页         🔥 个人栏专: 秒懂C语言 ⭐ 若在许我少年时,一两黄金一两风      目录 一、二分查找的思路  二、思路分析 2.1定义变量 2.2逻辑分析 三、代码实现 总结         二分查找是一种高效的查找算法,尤其适用于有序数组。它的基

    2024年02月04日
    浏览(35)
  • 【C语言】二分查找

    在 有序表 中,每次都取 中间元素 作为比较的对象。 如果给中间值与给定值相等,则查找成功,返回该元素的下标/索引; 如果中间值大于给定值,则在中间值的右半区间继续查找; 如果中间值小于给定值,则在中间值的左半区间继续查找; 确定了该元素所在范围那么范围

    2024年02月06日
    浏览(37)
  • C语言之二分查找

    目录 一、二分查找算法 二、分支语句中应注意的小点   所谓二分查找,就是要在一组 有序的数列 中,查找给定的数是否在此数列中。 最主要的步骤有三个: 1.确定被查找的范围的左右下标left、right 2.根据left和right,确定中间元素的下标mid 3.根据mid锁定的元素和查找的元素

    2023年04月22日
    浏览(38)
  • 一个几乎全民都会的算法——二分查找

    20年前央视2套有一档叫《幸运52》的综艺节目,其中一个环节叫《幸运超市》,每一期已故著名主持人咏哥都会给佳宾们出示几个商品,凡是佳宾猜中价格的,就能获赠这件商品。这档节目红极一时,被很多地方卫视节目复制抄袭。 比如,上面这段视频(gif图)的配音这样的:

    2023年04月09日
    浏览(39)
  • 【C语言】二分查找(含图解)

    二分法:二分查找算法是一种在 有序数组 中查找某一特定元素的搜索算法,其思想就是不断地将有序查找表“一分为二”,逐渐缩小搜索区域,进而找到目标元素。 搜素过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜 素过程结束; 如果某一特定元素

    2024年02月07日
    浏览(38)
  • 牛刀小试---二分查找(C语言)

    二分查找,也叫折半查找,是一种在 有序数组 中查找特定元素的算法。它通过比较中间元素和目标值的大小,将查找范围缩小为一半,直到找到目标元素或者查找范围为空。  1. 确定搜索范围:首先,需要确定要在哪个区间内进行查找。这可以通过比较目标值与中间元素的

    2024年01月17日
    浏览(36)
  • 【单调栈】【二分查找】LeetCode: 2454.下一个更大元素 IV

    【动态规划】【广度优先】LeetCode2258:逃离火灾 单调栈分类、封装和总结 二分查找算法合集 给你一个下标从 0 开始的非负整数数组 nums 。对于 nums 中每一个整数,你必须找到对应元素的 第二大 整数。 如果 nums[j] 满足以下条件,那么我们称它为 nums[i] 的 第二大 整数: j i n

    2024年02月03日
    浏览(42)
  • c语言经典算法—二分查找,冒泡,选择,插入,归并,快排,堆排

             1、前提条件:数据有序,随机访问;          2、实现:递归实现,非递归实现          3、注意事项:                 循环退出条件:low =high,low = high.说明还有一个元素,该元素还要与key进行比较                 mid的取值:mid=(low + high)/2;mid = l

    2024年02月05日
    浏览(43)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包