精华内容
下载资源
问答
  • C语言实现折半查找
    2019-09-30 17:08:45

    **

    C语言实现折半查找

    以及纠结了我好久的一个坑
    **
    简单粗暴,来,吸纳看代码

    
    
    int Search(int nums[], int numssize, int target)
    {
    
    	assert(nums != NULL);//重点:对指针进行判空
    	int left = 0;
    	int right = numssize;
    	while (left <= right)
    	{
    		int mid = (left + right) / 2;//mid不能定义在while外面,不然每执行一趟循环mid还是等于初始值2
    		if (nums[mid] > target)
    		{
    			right = mid - 1;
    		}
    		else if (nums[mid] < target)
    		{
    			left = mid + 1;
    		}
    		else
    		{
    			return mid;
    		}
    	}
    	return -1;
    }
    int main()
    {
    	int nums[] = { 2, 4, 6, 8, 9 };
    	int numssize = sizeof(nums) / sizeof(nums[0]) - 1;
    	int target = 7;
    	int index = Search(nums, numssize, target);
    	printf("%d\n", index);
    	return 0;
    }
    

    注意:
    · 第一个注释,对指针判空
    · 第二个注释mid要写在循环里不然就成死循环了。。
    不知道为啥,我代码vs都跑过了,在leetcode里执行也没问题,就是提交的时候就会说我执行有错,提示错在第29行,可是问我代码并没有29行(小生bb),问同学ing。。。
    不管怎样,加油鸭!!!

    更多相关内容
  • 折半查找法也叫做二分查找,顾名思义,就是把数据分成两半,再判断所查找的key在哪一半中,再重复上述步骤知道找到目标key; 注意:折半查找法仅适用于对已有顺序的数组、数据进行操作!!! 很显然,折半查找法相...
  • C语言折半查找法(超详细)

    千次阅读 多人点赞 2021-11-17 23:03:33
    折半查找法仅适用于对已有顺序的数组、数据进行操作!!!(从小到大)自我总结:折半查找法就是相当于(通过改变low或high的大小)把中间位置指到了key那个数那里,所以mid应该处于循环里面,即mid=(high+low)/2...

    折半查找法仅适用于对已有顺序的数组、数据进行操作!!!(从小到大)自我总结:折半查找法就是相当于(通过改变low或high的大小)把中间位置指到了key那个数那里,所以mid应该处于循环里面,即mid=high+low/2。注意:lowmidhigh都要与下标绑定,也就是说它们就是下标。且循环条件是:high>=low.

    同时注意:若原来数组是由小到大排列的则:

          mid=(high+low)/2;

                if(key<a[mid])//说明要找的值在左边

                high=mid-1;

                else if(key>a[mid])//说明要找的值在mid右边

                low=mid+1;//最小值的位置往右进一位

    若原来数组是由大到小排列的则:

    mid=(high+low)/2;

                if(key>a[mid])//注意是由大到小排列 ,所以此时keyamid 左边,故high=mid-1

                high=mid-1;

                else if(key<a[mid])//注意是由大到小排列,所以此时keyamid】右边,故low=mid+1

                low=mid+1;

    当然在下面这个代码中,也可以用选择排序法和冒泡法来对任意数组进行排序,然后在应用此函数,保证折半查找法的前提是排好序了。

    #include<stdio.h>
     void zb(int key,int a[],int n)//key表示要找的数,a表示数组,n表示数组元素个数 
     {
     	int i,high,low,mid;
     	int count1=0,count=0;
     	low=0;
     	high=n-1;
     	while(high>=low)//保证右下标不小于左下标 
     	{	
    		count++;
    		mid=(high+low)/2;//总的来说变得是中间位置相当于把中间位置移到了key那个数那里,所以mid应该处于循环里面 
     		if(key<a[mid])//说明key在a【mid】的左半边 ,那么最右边的high下标就可以在下标mid基础上往左进一个单位了
    		high=mid-1;
     		else if(key>a[mid])//说明key在a【mid】的右半边 ,那么最左边的low下标就可以在下标mid基础上往右进一个单位了 
     		low=mid+1;
    		if(key==a[mid])
    		{
    			printf("元素找到了!!!\n一共查找了%d次\n它处于a[%d]位置上\na[%d]=%d\n",count,mid,mid,key);
    			count1++;
    			break;
    		}
    	}
    	 if(count1==0)
    	 printf("元素不存在!!!\n");
     }
     int main ()
     {
     	int key,n,a[100];
     	int i;
     	void zb(int key,int a[],int n);//声明定义函数 
     	printf("请输入数组元素个数:\n");
     	scanf("%d",&n);
     	printf("请输入(从小到大)所有数组元素:\n");
     	for(i=0;i<n;i++)
     	{
     		scanf("%d",&a[i]);
    	 }
    	 printf("请输入要查找的数:\n");
    	 scanf("%d",&key);
    	 zb(key,a,n);
    	 printf("\n");
    	 return 0;
     }

    展开全文
  • 使用折半查找,输入一个整数,查找是否在数组中,如在给出下标,否则-1
  • C语言折半查找

    2021-07-09 17:16:50
    对于一个已经排好序的数组(上一篇博客 冒泡排序 讲到如何给数组排序),要查找其中一个元素,除了从第一个元素到最后一个元素依次遍历以外,还可以使用折半查找折半查找的思路是这样的(以升序数组为例): ...

    对于一个已经排好序的数组(上一篇博客 冒泡排序 讲到如何给数组排序),要查找其中一个元素,除了从第一个元素到最后一个元素依次遍历以外,还可以使用折半查找。

    折半查找的思路是这样的(以升序数组为例):

    1. 开始先从中间(最左边元素下标加最右边元素下标除以二)的元素开始找,如果中间的元素小于要找的目标元素,则说明目标元素在中间元素的右边,此时我们以中间元素的下标为左边元素下标,重复上面的过程。
    2. 如果中间的元素大于要找的目标元素,则说明目标元素在中间元素的左边,此时我们以中间元素的下标为最右边元素下标,重复上面的过程。
    3. 找到以后返回下标,如果左边元素下标大于右边元素下标,则说明没有找到。

    具体代码是这样的:

    #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;//中间元素下标
    	while (left <= right)
    	{
    		mid = (left + right) / 2;
    		if (arr[mid] > key)
    		{
    			right = mid - 1;
    		}
    		else if (arr[mid] < key)
    		{
    			left = mid + 1;
    		}
    		else
    			break;
    	}
    	if (left <= right)
    	{
    		printf("找到了,下标是%d\n", mid);
    	}
    	else
    	{
    		printf("找不到\n");
    	}
    
    	return 0;
    }
    

    在这里插入图片描述
    将要找的元素改成11:
    在这里插入图片描述

    我们也可以将这个查找的方法写成函数:

    int bin_search(int arr[], int left, int right, int key) 
    {
     int mid = 0;
     while(left<=right)
     {
     mid = (left+right)>>1;
     if(arr[mid]>key)
     {
     right = mid-1;
     }
     else if(arr[mid] < key)
     {
     left = mid+1;
     }
     else
     return mid;//找到了,返回下标
     }
     return -1;//找不到
    }
    

    相比于依次遍历的方法,折半查找的效率会高很多,因为对于一个元素数量为n的数组,普通遍历需要查找n次,而折半查找只需查找 l o g 2 n {log_2{n}} log2n次(因为折半查找每次查找一半, 2 l o g 2 n 2^{log_2{n}} 2log2n=n,所以只需查找 l o g 2 n {log_2{n}} log2n次即可)。

    展开全文
  • 数据结构 折半查找 实例代码: /* 名称:折半查找 语言:数据结构C语言版 编译环境:VC++ 6.0 日期: 2014-3-26 */ #include #include #include <windows> #define N 11 // 数据元素个数 typedef int Key...
  • 数据结构C语言折半查找之递归和循环算法~

    1.递归结构折半查找

    int BSearch(int a[], int x, int low, int high)
    {
    	int mid;
    	if (low > high)
    		return -1;
    	mid = (low + high) / 2;
    	if (a[mid] == x)
    		return mid;
    	else if (x > a[mid])
    		return BSearch(a, x, mid + 1, high);
    	else
    		return BSearch(a, x, low, mid - 1);
    
    }

    2.循环结构折半查找

    循环结构折半查找利用顺序表完成

    需声明如下函数

    /*初始化顺序表*/
    void ListInitiate(seqlist* s);
    
    /*插入顺序表元素*/
    //插入成功返回1,否则返回0
    int ListInsert(seqlist* s, int index,int x);
    
    
    /*折半查找*/
    //查找成功返回该元素位置,否则返回-1
    int BinarySearch(seqlist s, DataType x);
    

    对顺序表的定义在只之前文章已经写过,此处只介绍折半查找算法

    /*折半查找*/
    //查找成功返回该元素位置,否则返回-1
    int BinarySearch(seqlist s, DataType x)
    {
    	int low = 0, high = s.size - 1, mid;
    	while (low <= high)
    	{
    		mid = (low + high) / 2;
    		if (s.data[mid].key== x.key)
    			return mid;
    		else if (s.data[mid].key < x.key)
    			low = mid + 1;
    		else if (s.data[mid].key > x.key)
    			high = mid - 1;
    	}
    	return -1;
    }

    例题:

    在保存于数组的 100 个有序数据元素中查 找数据元素 x 是否存在。数据元素 x 要包含两种情况:一种是数据元 素 x 包含在数组中;另一种是数据元素 x 不包含在数组中。

    设计出递归算法和循环结构两种实现方法的折半查找函数

    1.递归算法实现

    #include<stdio.h>
    int BSearch(int a[], int x, int low, int high)
    {
    	int mid;
    	if (low > high)
    		return -1;
    	mid = (low + high) / 2;
    	if (a[mid] == x)
    		return mid;
    	else if (x > a[mid])
    		return BSearch(a, x, mid + 1, high);
    	else
    		return BSearch(a, x, low, mid - 1);
    
    }
    int main()
    {
    	int a[] = { 1,2,3,4,5,6,7,8 };
    	int x = 9;
    	int b;
    	b = BSearch(a, x, 0, 7);
    	if (b != -1)
    		printf("x在数组a中,x的值为%d,下标为%d",x,b);
    	else
    		printf("x的值为%d,x不在数组中",x);
    }

    程序运行结果如下

     2.循环结构算法

    #include<stdio.h>
    #include"seqlist.h"  //包含顺序表头文件和折半查找算法
    
    //定义要查找的数据元素(关键字)
    typedef int KeyType;
    
    typedef struct
    {
    	KeyType key;
    }DataType;
    int main()
    {
    	seqlist mylist;
    	DataType x;
    	x.key = 8;
    	int i;
    	ListInitiate(&mylist);
    	for ( i = 0; i < MaxSize; i++)
    	{
    		ListInsert(&mylist, i, i+1);
    	}
    	int a=BinarySearch(mylist, x);	
    	
    	if (a != -1)
    	{
    		printf("要查找的元素是%d", mylist.data[a]);
    	}
    	else
    	{
    		printf("要查找的元素是%d\n", x.key);
    		printf("元素不在数组中");
    	}
    		
    
    	
    }

    运行结果如下

     

    展开全文
  • 折半查找C语言代码(C语言)

    千次阅读 2020-02-27 11:24:05
    源码如下: 首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表...//折半查找,前提是有序 #include <stdio.h...
  • //二分查找函数输入:低位、高位、目标值返回:true/falsebool BSearch(int low,int high,int target){//标志位用于返回函数值,默认为false,查找成功置为truebool flag = false;//每次循环都是一次判定//成功:...
  • 折半查找,顾名思义,就是一组有顺序的数,按照比较大小的方法找出某一个数,类似二分法代码如下:#include#includevoidfind(intarr1[],intkey,intright){intleft=0,mid;while(left<=right){mid=(left+right)/2;...
  • C语言——折半查找

    千次阅读 2022-03-29 21:02:48
    C语言——折半查找折半查找法,顾名思义就是一种查找的方法。优点是其比较次数少,查找速度快,平均性能好。缺点是其要求的待查表必须是有序表,且插入删除比较困难。因此,折半查找法适用于不经常变动并且查找...
  • C语言简单实现折半查找

    万次阅读 多人点赞 2018-08-16 08:27:12
    折半查找,又称作二分查找。这个查找的算法的特点,就是,要求数据要是有序的。 1 ,存储结构一定是顺序存储 2 ,关键字大小必须有序排列 算法思想:折半查找只能在有序数列中进行,将待查找的数据与有序数列...
  • 文章目录前言一、思路二、代码的实现 前言 当我们需要在一堆有序的数组中(二分查找只支持有序数组)找到某个元素的位置,即下标的时候,最常见的是遍历的方法(暴力求解法),一个个核对,不相等就跳到下一个,...
  • printf("请输入要查找的数:"); int b; scanf("%d",&b); int low = 0; int high = sizeof(a)/sizeof(a[0]);//获取数组的长度 int temp; while(low < high) { temp = (low + high)
  • 折半查找代码

    2015-06-14 17:09:52
    折半查找是一种数据结构算法 非常有用 我们用C语言实现了查找 简单有效
  • 折半查找(C语言)

    千次阅读 2021-06-03 21:53:53
    折半查找法, 也称为二分查找法, 二分搜索, 是一种在有序数组中查找某一特定元素的搜索算法.搜索过程中从数组的中间元素开始, 如果中间元素正好是要查找的元素, 则搜索过程结束;如果某一特定元素大于或者小于中间...
  • 二分查找首先最最重要就是你要查询的目标数组是一个有序的数组 直接上代码 #include <stdio.h> int binarysearch(int arr[], int size, int key) { int left = 0; int right = size - 1; while (left &...
  • 折半查找(c语言

    2021-07-22 11:48:54
    折半查找描述格式样例题解及注释 描述 给定一个长度为n(n≤10000)的单调递增整数数列,和要查找的整数,利用折半查找算法找到该数据。输出成功找到该数据所需的比较次数;如果查找未成功,则输出0。 比如有序列: ...
  • 程序员在程序设计时常常需要对存储在数组中的大量数据进行处理,如排序、查找等。使用数据库时,用户可能...上次我们已经介绍了一种最基础的查找算法——线性查找(顺序查找)这次我们来介绍一种查找算法:折半查找
  • 复制代码 代码如下:#include int bin_search(int key[],int low, int high,int k){int mid;if(low>high){return -1;}else{mid = (low+high) / 2;if(key[mid]==k)return mid;if(k>key[mid])return bin_search...
  • c语言折半查找

    千次阅读 2019-10-15 09:17:48
    # include int BinSearch ( int arr [ ] , int len , int key ) { int low = 0 ; //起始元素 int high ...//右边查找 ...//查找值为0~14 ...运行结果如下:(-1表示未查找到该值)
  • 目录 一、线性表结构 两个类的定义 二、线性表的初始化以及根据输入的元素建立线性表 1.线性表的初始化,初始化一个空...五、折半查找(非递归)Search3函数 六、折半查找(递归)Search4函数 七、显示输出函数 Show函数
  • 本文实例为大家分享了C语言实现顺序表的顺序查找和折半查找的具体代码,供大家参考,具体内容如下 顺序查找: #include using namespace std; int SeqSearch(int r[],int n,int k) { r[0]=k;//下标0用作哨兵存放...
  • 二分查找的具体实现,图解二分查找流程。
  • C语言折半查找法(二分法)的实现

    万次阅读 多人点赞 2019-03-31 20:40:15
    折半查找法也叫做二分查找,顾名思义,就是把数据分成两半,再判断所查找的key在哪一半中,再重复上述步骤知道找到目标key; 注意:(咳咳,敲黑板)折半查找法仅适用于对已有顺序的数组、数据进行操作!!! 很...
  • 折半查找-C语言实现

    千次阅读 2020-06-06 16:40:22
    折半查找要求表中数据是有序的。 折半查找的循环条件是low<=high而不是low<high,为low=high时,查找区间还有最后 一 个结点, 还要进 一 步比较。 //折半查找 int SearchBin(SqList &L, int key){ ...
  • 折半查找.C语言系统上机代码

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,633
精华内容 1,453
关键字:

c语言折半查找代码

友情链接: MFC.rar