牛刀小试---二分查找(C语言)

题目:在给定的升序数组中查找指定的数字n,并输出其下标

代码举例:

#include <stdio.h>
int main()
{
	int arr[] = { 1,2,3,4,5,6,7,8,9,10 };//给定的升序数组
	int left = 0;//定义左下标
	int right = sizeof(arr) / sizeof(arr[0]) - 1;//定义右下标
	int key = 7;//要找的数字
	int mid = 0;//记录中间元素的下标
	int find = 0;//定义真假,用与判断输出
	while (left <= right)
	{
		mid = (left + right) / 2;//表示中间元素的下标
		if (arr[mid] > key)//中间下标所在元素大于要找的数字
		{
			right = mid - 1;//则右下标改变
		}
		else if (arr[mid] < key)//中间下标所在元素小于要找的数字
		{
			left = mid + 1;//则左下标改变
		}
		else//中间下标所在元素就是要找的数字
		{
			find = 1;//真,找到了
			break;//跳出循环
		}
	}
	//输出
	if (1 == find)
		printf("找到了,下标是%d\n", mid);
	else
		printf("找不到\n");
	return 0;
}

运行结果:

题目解析:

1. 明确概念:

二分查找,也叫折半查找,是一种在有序数组中查找特定元素的算法。它通过比较中间元素和目标值的大小,将查找范围缩小为一半,直到找到目标元素或者查找范围为空。

2. 知其原理(步骤)

 1. 确定搜索范围:首先,需要确定要在哪个区间内进行查找。这可以通过比较目标值与中间元素的大小来确定。如果目标值小于中间元素,则可以确定目标值只可能存在于前半部分;如果目标值大于中间元素,则可以确定目标值只可能存在于后半部分;如果目标值等于中间元素,则可以直接找到目标值。


 2.划分区间:根据目标值与中间元素的比较结果,可以将搜索范围划分为两个子区间。如果目标值小于中间元素,则将搜索范围缩小为前半部分;如果目标值大于中间元素,则将搜索范围缩小为后半部分。

 3.在确定了新的搜索范围后,重复步骤1,2,直到找到目标值。

3. 思路方法:

知道其原理,将其转化为代码,通过定义左右下标,确定搜索范围,通过定义中间元素下标,确定中间元素,通过定义变量key表示所找目标值,通过定义变量flag,用于判断输出;比较目标值与中间元素的大小,根据目标值与中间元素的比较结果,通过左右下标的改变,缩小搜索范围,通过while循环实现重复;最后通过变量flag进行判断输出。

结言:本文将一维数组的使用与循环相结合,实现二分查找,进一步巩固数组和循环相关知识。

相关推荐

  1. C语言-二分查找

    2024-01-17 00:26:01       24 阅读
  2. [C语言]二分查找

    2024-01-17 00:26:01       17 阅读
  3. C语言----数组----二分查找

    2024-01-17 00:26:01       11 阅读
  4. 王道c语言-顺序查找二分查找

    2024-01-17 00:26:01       20 阅读

最近更新

  1. TCP协议是安全的吗?

    2024-01-17 00:26:01       17 阅读
  2. 阿里云服务器执行yum,一直下载docker-ce-stable失败

    2024-01-17 00:26:01       16 阅读
  3. 【Python教程】压缩PDF文件大小

    2024-01-17 00:26:01       15 阅读
  4. 通过文章id递归查询所有评论(xml)

    2024-01-17 00:26:01       18 阅读

热门阅读

  1. flutter-基本功能总结

    2024-01-17 00:26:01       30 阅读
  2. c 小熊猫 c++ IDE编译ffmpeg 设置

    2024-01-17 00:26:01       37 阅读
  3. ubuntu22.04 virt-manager bridge虚拟机ip 一样

    2024-01-17 00:26:01       36 阅读
  4. C语言实现双向循环链表

    2024-01-17 00:26:01       38 阅读
  5. 01-k8s学习笔记之认识 Kubernetes

    2024-01-17 00:26:01       33 阅读
  6. 计算机网络(第六版)复习提纲1

    2024-01-17 00:26:01       38 阅读
  7. ChatGPT 淘金潮(全)

    2024-01-17 00:26:01       910 阅读
  8. RabbitMQ的高可用机制

    2024-01-17 00:26:01       35 阅读
  9. [Docker] 的常用命令

    2024-01-17 00:26:01       26 阅读