【二分查找】详细图解

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

目录

一.什么是二分查找法?

二.算法要求

三.算法思想

图解(要找的数k的值为3)

 参考代码


一.什么是二分查找法?

二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序储存结构,而且表中元素按关键字有序排列。 

二.算法要求

1.必须是有序排列。

三.算法思想

例如数列   arr[]={1,2,3,4,5,6,7,8,9}          查找的数为k=3;

这里的left,right,mid记录的是数组下标

1.用left指向数列最左边的数(1),即left=0;

2.用right指向数列中最右边的数(9),即right=8;

3.用mid记录下标为(left+right)/2的数,即数组中间的数(5);

这一步完成后,就是把arr[]数组分为了两个子数组,用arr[mid]隔开

即:      {1,2,3,4}           5         {6,7,8,9}

4.用arr[mid]与目标数k的大小进行比较,有三种情况

(1)arr[mid]=k;  即找到了

  (2)如果k比arr[mid](即中间的那个数)大,则说明目标数(k)右边的那个子数组中,所以就变成了在右边数组中找目标元素;方法和上面的类似,所以我们只需要将left指向改变为右边那个子数组的最左边的元素,即left=mid+1;

  (3)同理,如果k比arr[mid]小,则说明目标数(k)在左边的那个子数组中,所以就变成了在左边数组中找目标元素;我们只需要将right指向改变为左边那个子数组的最右边的元素,即right=mid-1;

5.只需要重复第四步的操作就可以把k的值的位置找到;

图解(要找的数k的值为3)

【二分查找】详细图解

 参考代码

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>

int main()
{
	int arr[] = { 1,2,3,4,5,6,7,8,9,10};
	int k = 0;
	scanf("%d",&k);
	int left = 0;
	int right = sizeof(arr) / sizeof(arr[0]) - 1;
	while (left < right)
	{
		int mid = (left + right)/2;
		if (arr[mid] == k)
		{
			printf("找到了,下标为%d\n",mid);
			break;
		}
		else if (arr[mid] < k)
		{
			left = mid + 1;
		}
		else
		{
			right = mid-1;
		}
	}
	if (left > right)
	{
		printf("没找到,数不在该数列上\n");
	}

	return 0;
}

输出

【二分查找】详细图解

 


!!!!文章来源地址https://www.toymoban.com/news/detail-499367.html

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

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

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

相关文章

  • Java:什么是向上转型与向下转型(详细图解)

    目录 一、什么是向上转型 1、概念 2、代码示例 3、向上转型的优缺点 二、什么是向下转型 1、向下转型的概念 ​编辑 2、代码示例 三、向下转型的缺点及 instanceof 的使用 1、向下转型的缺点 2、instanceof的使用 向上转型就是 创建一个子类对象 ,将其 当成父类对象来使用 。

    2024年03月23日
    浏览(43)
  • 问题 C: 二分查找右侧边界(C++)(二分查找)

    1.题目描述 2.AC 问题 C: 二分查找右侧边界 时间限制: 1.000 Sec  内存限制: 128 MB 提交 状态 题目描述 请在一个有序不递减的数组中(数组中的值有相等的值),采用二分查找,找到最后1次出现值x的位置,如果不存在x请输出-1。 请注意:本题要求出q个x,每个x在数组中第一

    2024年02月03日
    浏览(45)
  • 二分查找入门教学(动态讲解图、模拟示例、二分查找代码讲解)

    博客昵称: 吴NDIR 个人座右铭:得之淡然,失之坦然 作者简介:喜欢轻音乐、象棋,爱好算法、刷题 其他推荐内容: 计算机导论速记思维导图 其他内容推荐: 五种排序算法 在这个愉快的周末让我们聊一下 二分查找 吧!二分查找是一种很常用的算法,可帮助我们在有序数

    2023年04月18日
    浏览(46)
  • 二分查找(整数二分)

    二分法,即二分搜索法,是通过不断缩小解可能存在的范围,从而求得问题最优解的方法。 例如,如果一个序列是有序的,那么可以通过二分的方法快速找到所需要查找的元素,相比线性搜索要快不少。 此外二分法还能高效的解决一些单调性判定的问题。 二分的关键不在于

    2024年02月08日
    浏览(51)
  • 【算法】二分查找(整数二分和浮点数二分)

    大家好!今天我们来学习二分查找算法,这是一种效率很高的算法哦! 目录 1. 整数二分 2. 整数二分模板 3. 整数二分模板题 3.1 洛谷 P2249 【深基13.例1】查找 3.2 Acwing789. 数的范围 4. 浮点数二分 5. 浮点数二分模板 6. 浮点数二分模板题 6.1 Acwing 790.数的三次方根 6.2 洛谷 P1024 [

    2024年02月10日
    浏览(51)
  • C++二分算法(二分查找&二分答案)细节详解

     二分算法可以分为 二分查找 和 二分答案 。 以在一个 升序数组 中查找一个数为例。它每次考察数组当前部分的 中间元素 ,如果中间元素刚好是要找的,就结束搜索过程;如果中间元素小于所查找的值,那么左侧的只会更小,不会有所查找的元素,只需到右侧查找;如果

    2024年02月08日
    浏览(52)
  • 【Python查找算法】二分查找、线性查找、哈希查找

    目录 1 二分查找算法  2 线性查找算法 3 哈希查找算法         二分查找(Binary Search)是一种用于在有序数据集合中查找特定元素的高效算法。它的工作原理基于将数据集合分成两半,然后逐步缩小搜索范围,直到找到目标元素或确定目标元素不存在。 以下是二分查找的

    2024年02月08日
    浏览(51)
  • 【算法系列篇】二分查找——这还是你所知道的二分查找算法吗?

    在生活中,我们往往会遇到在数组中查找某个确定的元素的时候,通常我们会选择使用暴力解法,这样虽然简单,但是时间复杂度是O(N),时间效率比较低。那么是否有方法可以使得在具有二段性的数组中找某一特定的元素的时间复杂度低于0(N)呢?答案是肯定的,当我们可以

    2024年02月11日
    浏览(51)
  • 二分查找--查找整数位置

    描述 二分查找 又叫 折半查找。它采用的是\\\"分治策略\\\"。 给出非降序排列的 n 个整数,查找是否存在某个整数,如果存在,则输出其位置。 输入描述 第一行是一个整数 n(0n≤200000) 表示整数的个数。 接下来是 n 个整数,每个整数之间用一个空格分隔。 接下来一行是一个

    2024年02月13日
    浏览(43)
  • 数据结构算法--1 顺序查找二分查找

    顺序查找时间复杂度为O(n) 我们可以借助Python中的函数enumerate,通过enumerate遍历列表返回其索引和值 也可以通过列表长度依次遍历: 但是二分查找时间复杂度为O(logn):

    2024年02月12日
    浏览(54)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包