精华内容
下载资源
问答
  • 2021-12-08 21:03:14
    #include<iostream>
    #include <stdlib.h>
    using namespace std;
    #define SPACE 100
    //顺序查找表的定义
    typedef int ElemType;
    typedef struct {
    	ElemType *elem; //数据元素存储空间基址,0 号单元留空
    	int length; //表长度
    }SSTable;
    //创建查找表
    void CreateTable(SSTable &ST) {
    	//根据用户输入的长度,创建查找表空间,即为 elem 数组分配空间
    	//利用循环,提示用户输入查找表数据,并存储在查找表内
    	//为查找表长度赋值
    	cout << "请输入查找表的长度";
    	cin >> ST.length;
    	ST.elem = new ElemType[SPACE];//动态分布一个数组空间
    	cout << "请输入数据";
    	for (int i=1; i< ST.length; i++)
    	{
    		cin >> ST.elem[i];
    	}
    }
    //输出查找表元素
    void Traverse(SSTable ST)
    {
    	for (int i=1; i <  ST.length; i++)
    		cout << ST.elem[i] << " ";
    	cout << endl;
    	//利用循环依次输出查找表元素
    }
    //在顺序表 ST 中顺序查找等于 key 的数据元素。
    //若找到,则返回该元素在表中的位置,否则返回 0 
    int Search_Seq(SSTable &ST, ElemType key) {
    	ST.elem[0] = key;//设立一个哨兵
    	int i = ST.length;
    	for ( i; ST.elem[0] != ST.elem[i]; i--);//不用比较2次,既比较是不是越界,又比较是不是要找的数
    	
    	return i ;
    	
    	
    }
    //在有序表 ST 中折半查找等于 key 的数据元素。
    //若找到,则返回该元素在表中的位置,否则返回 0
    int Search_Bin(SSTable &ST, ElemType key) {
    	int low, high, mid;
    	low = 1;
    	high = ST.length;
    	mid = (low + high) / 2;
    	while (key != ST.elem[mid] && low <= high)
    	{
    		if (key < ST.elem[mid]) 
    			high = mid - 1;
    		else 
    			low = mid + 1;
    		mid= (low + high) / 2;
    	}
    	if (low <= high)
    		return mid;
    	else 
    		return 0;
    
    }
    int main(void)
    {
    	SSTable ST;
    	int c = 0;
    	ElemType key;
    	while (c != 3) {
    		cout << endl << "1. 顺序查找法";
    		cout << endl << "2. 折半查找法";
    		cout << endl << "3. 退出";
    		cout << endl << "选择功能(1~3):";
    		cin >> c;
    		switch (c)
    		{
    		case 1:
    			CreateTable(ST);
    			Traverse(ST);
    			cout << "请输入要查找的数据:";
    			cin >> key;
    			cout<<Search_Seq(ST, key);
    			break;
    		case 2:
    			CreateTable(ST);
    			Traverse(ST);
    			cout << "请输入要查找的数据:";
    			cin >> key;
    			cout<<Search_Bin(ST, key);
    			break;
    		case 3:
    			cout << "结束操作" << endl;
    			break;
    		}
    	}
    }

    更多相关内容
  • 以下小编就为大家介绍两种实现方法。第一种方法是,选择排序法+循环折半查找法。第二种方法是,冒泡排序法+递归折半查找法。需要的朋友可以过来参考下,希望对大家有所帮助
  • 折半查找的实现 要求: 1.若查找成功,返回元素在有序数组中的位置和查找次数; 2.若查找失败,返回出错标志和查找次数。 //low应从0开始,因为设置的数组下标从0开始 //虽然mid不变,但是当key为首元素时,mid为1也...

    折半查找的实现

    要求:

    1.若查找成功,返回元素在有序数组中的位置和查找次数;

    2.若查找失败,返回出错标志和查找次数。

    //low应从0开始,因为设置的数组下标从0开始
    //虽然mid不变,但是当key为首元素时,mid为1也就是第二元素,导致找不到第一个元素。
    #include <iostream>
    using namespace std;
    typedef int Status;
    typedef int KeyType;
    typedef int InfoType;
    typedef struct {
    	KeyType key;
    	InfoType otherinfo;
    }ElemType;
    typedef struct {
    	ElemType* R;
    	int length;
    }SSTable;
    
    //对顺序表初始化
    Status InitSSTable(SSTable& ST)
    {
    	ST.R = new ElemType[100];
    	if (!ST.R) exit(OVERFLOW);
    	ST.length = 0;
    	return 1;
    }
    //顺序表的建立
    void CreateSSTable(SSTable& ST)
    {
    	int n;
    	cout << "请输入顺序表的元素个数:";
    	cin >> n;
    	cout << "请依次输入元素:";
    	for (int i = 0; i < n; i++)
    	{
    		cin >> ST.R[i].key;
    		ST.length++;
    	}
    }
    //顺序表的显示
    Status SSTableShow(SSTable ST)
    {
    	for (int i = 0; i < ST.length; i++)
    	{
    		cout << ST.R[i].key << " ";
    	}
    	cout << endl;
    	return 1;
    }
    //折半查找
    int count0;
    Status Search_Bin(SSTable ST, KeyType key)
    {
    	int low = 0;
    	int high = ST.length-1;
    	int mid = 0;
    	while (low<=high)
    	{
    		count0++;
    		mid = (low + high) / 2;
    		if (key == ST.R[mid].key)
    		{
    			return mid+1;
    		}
    		else if (key<ST.R[mid].key)
    		{
    			high = mid - 1;
    		}
    		else
    		{
    			low = mid + 1;
    		}
    	}
    	return -1;
    }
    
    
    int main()
    {
    	SSTable ST;
    	InitSSTable(ST);
    	CreateSSTable(ST);
    	SSTableShow(ST);
    	int key;
    	cout << "输入要查找的元素:";
    	cin >> key;
    	int address = Search_Bin(ST, key);
    	if (address == -1)
    	{
    		cout << "查找失败,查找次数为:"<<count0;
    	}
    	else
    	{
    		cout << "该元素在" <<address<<"号位置。"<<"比较"<<count0<<"次"<< endl;
    	}
    
    	return 0;
    }
    
    展开全文
  • 顺序查找和折半查找

    2017-12-07 20:43:40
    用顺序存储结构表示查找表,实现以下运算要求: (1)建立一个整数数据文件 datafile; (2)从文件 datafile 读取数据,并导入一维... (4)先对数组中的元素进行排序,分别用递归和非递归两种方式实现折半查找方法。
  • 折半查找c++的两种方法实现

    千次阅读 2017-03-01 11:49:33
    折半查找在数据结构算法中是一个比较实用的算法。 但是它是一个只能用于查找有顺序的数,这并不影响它的使用,可以先实现一个排序再进行查找。 折半查找比较简单,但是注意的点也比较多。 下面我将用递归和非递归两...

    折半查找在数据结构算法中是一个比较实用的算法。

    但是它是一个只能用于查找有顺序的数,这并不影响它的使用,可以先实现一个排序再进行查找。

    折半查找比较简单,但是注意的点也比较多。

    下面我将用递归和非递归两种方法进行实现。


    非递归:

    在取头尾时有两种选择:左闭右闭[begin,end],左闭右开[begin,end)

    这两个不同的选择会影响后面的条件判断

    时间复杂度O(log2N)

    int BinarySearch(int len,int* arr,int x)
    {
        assert(arr);
    	int begin = arr[0];
    	int end = len;
    	while (begin < end)
    	{
    		int mid = ((end - begin) >> 2) + begin;
    		if (arr[mid] < x)
    		{
    			begin = mid + 1;
    		}
    		else if (arr[mid]>x)
    		{
    			end = mid - 1;
    		}
    		else
    		{
    			return mid;
    		}
    		return -1;
    	}
    }
    
    
    int main()
    {
    	int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    	int len = sizeof(arr) / (sizeof(arr[0]));
    	cout << BinarySearch(10, arr, 1) << endl;
    	cout << BinarySearch(10, arr, 2) << endl;
    	cout << BinarySearch(10, arr, 3) << endl;
    	cout << BinarySearch(10, arr, 4) << endl;
    	cout << BinarySearch(10, arr, 5) << endl;
    	cout << BinarySearch(10, arr, 6) << endl;
    	cout << BinarySearch(10, arr, 7) << endl;
    	cout << BinarySearch(10, arr, 8) << endl;
    	cout << BinarySearch(10, arr, 9) << endl;
    	cout << BinarySearch(10, arr, 10) << endl;
    	cout << BinarySearch(10, arr, 11) << endl;
    }

    上面这个代码就是左闭右闭的情况,它在while里begin < end,在if里将mid + 1赋值给begin,mid-1赋值给end

    下面这个代码是左闭右开的情况,它在while里begin <= end,在if里将mid直接赋值给begin和end

    int BinarySearch(int len, int* arr, int x)
    {
    	assert(arr);
    	int begin = arr[0];
    	int end = len + 1;
    	while (begin <= end)
    	{
    		int mid = ((end - begin) >> 2) + begin;
    		if (arr[mid] < x)
    		{
    			begin = mid;
    		}
    		else if (arr[mid]>x)
    		{
    			end = mid;
    		}
    		else
    		{
    			return mid;
    		}
    		return -1;
    	}
    }
    
    int main()
    {
    	int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    	int len = sizeof(arr) / (sizeof(arr[0]));
    	cout << BinarySearch(10, arr, 1) << endl;
    	cout << BinarySearch(10, arr, 2) << endl;
    	cout << BinarySearch(10, arr, 3) << endl;
    	cout << BinarySearch(10, arr, 4) << endl;
    	cout << BinarySearch(10, arr, 5) << endl;
    	cout << BinarySearch(10, arr, 6) << endl;
    	cout << BinarySearch(10, arr, 7) << endl;
    	cout << BinarySearch(10, arr, 8) << endl;
    	cout << BinarySearch(10, arr, 9) << endl;
    	cout << BinarySearch(10, arr, 10) << endl;
    	cout << BinarySearch(10, arr, 11) << endl;
    }

    递归:

    同样非递归也分两种:左闭右闭和左闭右开,在这里我急就只介绍一种,选择了我喜欢的,在你们写的话只要分清楚两种就好
    int BinarrySearch(int* arr, int x, int begin, int end,int len)
    {
    	assert(arr);
    	begin = arr[0];
    	end = len + 1;
    	while (begin < end)
    	{
    		if (begin > end)
    		{
    			return -1;
    		}
    		int mid = begin + (end - begin) >> 1;
    		if (arr[mid] < x)
    		{
    			return BinarrySearch(arr, x, mid + 1, end);
    		}
    		else if (arr[mid] > x)
    		{
    			return BinarrySearch(arr, x, begin, mid - 1);
    		}
    		else
    		{
    			return mid;
    		}
    	}
    }

    我就是看着代码简单,根本没有当做一回事,以至于犯了错误,

    希望能对你们有用,千万不要小看任何一个简单的代码


    展开全文
  • 折半查找 C++

    2020-01-11 15:00:16
    二分查找 必须是有序的数列 从小到大 */ int BinarySeach(int a[], int Size, int target){ //左边的端点 一定要记得赋初值 int L = 0; //Size代表是数组的长度 R是代表数组的右端点 int R = Size - 1;...
    #include <bits/stdc++.h>
    using namespace std;
    /*
    二分查找 必须是有序的数列 从小到大
    */
    int BinarySeach(int a[], int Size, int target){
    	//左边的端点 一定要记得赋初值
    	int L = 0;
    	//Size代表是数组的长度 R是代表数组的右端点
    	int R = Size - 1;
    	while(L<=R){
    		//查找区间正中元素
    		int mid = L + (R - L) / 2;
    		if(target == a[mid])//已经查找到
    			return mid;//返回数组下标
    		else if(target > a[mid])
    			//因为a[mid]不是目标值 所以最左端要为mid再向右边挪移一个下标
    			L = mid + 1;
    		else 
    			R = mid - 1;
    	}
    	//如果要查找的数字 在数组中不存在
    	return -1;
    	/*
        	tip:对于int返回值类型的函数
           	    return 0:  一般是用在主函数 表示成功完成这个函数
                return -1:表示返回一个数值 一般用在子函数的结尾 表示该函数失败
                在这个子函数里面 没有查找到目标数值 则表示该函数失败
           */
    }
    int main()
    {
        int a[5] = {1,2,3,4,5};
        //求int类型的数组长度:sizeof(数组名) / sizeof(int) 不同的编译器 sizeof(int)是不一样的
        //对char数组的数组长度:strlen 需要引入头文件<string.h>
        printf("%d",BinarySeach(a,sizeof(a) / sizeof(int),5)) ;
        return 0;
    }	
    展开全文
  • 折半查找C++)

    2021-04-18 00:02:34
    折半查找 必须采用顺序存储结构,而且表中元素按关键字有序排列 原理 与中值比较,不断缩小区间范围 代码 #include using namespace std; int BinarySearch(int a[], int low, int high, int target) { while(low &...
  • 主要介绍了C++二分查找(折半查找)算法,结合实例形式详细分析了二分查找算法的原理、思想、实现方法与相关操作技巧,需要的朋友可以参考下
  • 折半查找(C++实现)

    千次阅读 2020-09-07 17:28:14
    折半查找 定义: 计算机科学中,折半搜索(英语:half-interval search),也称二分搜索(英语:binary search)、对数搜索(英语:logarithmic search),是一种在有序数组中查找某一特定元素的搜索算法。 搜索过程...
  • 折半查找c++

    2020-01-12 20:04:24
    using namespace std; /* ...思路 一个数字为a[i] 则在数组中查找出m - a[i]是否存在 */ bool findansewer(int a[], int now,int m){ int L = 0; int R = sizeof(a) / sizeof(int) - 1; boo...
  • C++折半查找的实现

    千次阅读 2020-09-05 17:18:40
    C++折半查找的实现 折半查找法也叫做二分查找,顾名思义,就是把数据分成两半,再判断所查找的key在哪一半中,再重复上述步骤知道找到目标key; 注意:(咳咳,敲黑板)折半查找法仅适用于对已有顺序的数组、数据进行...
  • C++折半查找代码实现

    2011-04-26 21:00:17
    折半查找C++代码实现,不需要积分下载啊
  • 二分查找(折半查找)简介与代码实现1.简介2.代码实现(C++)2.1.写法一(target在左闭右闭区间)2.2.写法二(target在左闭右开区间)3.代码检验 1.简介 二分查找的本质: 首先确定待查元素所在的范围,然后逐步...
  • C++算法——折半查找

    千次阅读 2021-04-15 17:02:50
    但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列 步骤 以下用数组1,2,3,4,5,6,7,8,9为例 此时我们查找3 1.首先我们的查找范围是全部,取两头下标的平均值 首先两头下标是0和n-1 ...
  • 折半查找要求线性表有序的 下面的这种查找算法采用递归实现,并没有利用折半查找有序的特性,所有下面的这种算法适用于其他特殊线性表; #include <iostream> using namespace std; //递归实现的查找算法 int...
  • 折半查找C/C++代码实现

    千次阅读 2020-06-28 14:16:18
    折半查找(二分查找): 折半查找的查找过程为:从表的中间记录开始,如果给定值和中间记录的关键字相等, 则查找成功;如果给定值大于或者小于中间记录的关键字, 则在表中大于或小于中间记录的那一半中查找,这样...
  • C/C++实现折半查找法(二分法)

    千次阅读 2021-01-19 11:59:40
    大家都知道有许多排序方法和对应的查找方法,今天我就来介绍一个超级高效的查找方法:折半查找法(也叫二分法)。但是首先说明,这种方法只是用于顺序排列的数组(重点哈)。 折半查找法 #define _CRT_SECURE_NO_...
  • 设定查找范围的下限low,上限high, 由此确定查找范围的中间位置mid; 中间位置的值等于待查的值,查找成功 中间位置的值小于待查的值,low=mid+1 中间位置的值大于待查的值,high=mid-1 直到low>high,查找失败...
  • 折半查找法是数据结构与算法的应用中相对重要的一个查找方法。还可以通过数学方法计算其时间复杂度。
  • 有序表的折半查找 贡献者:AdventureG 问题描述: 用有序表表示静态查找表时,通常检索函数可以用折半查找来实现。 折半查找的查找过程是:首先确定待查记录所在的范围,然后逐步缩小范围直到找到或者确定找不到...
  • C++实例:折半查找

    2020-07-15 08:27:36
    随机产生一个1~1000之间的整数,使用折半查找法找到该数,并且同时显示折半查找的次数。 #include<iostream> #include<cstring> #include<ctime> #include<cstdlib> #include<conio.h&...
  • 折半查找 C++template

    2020-05-07 21:25:05
    #include <stdio.h> #include <assert.h> #define LEN 8 int a[LEN] = { 2, 5, 7, 13, 14, 16, 17, 21 }; int is_sorted() { int i, sorted = 1; for (i = 1; i < LEN; i++) ...
  • C++顺序表折半查找

    2020-03-09 16:49:21
    折半查找:又称二分查找,适用于有序的顺序表。 先将中间位置元素与Key进行比较 若相等,则返回中间位置下标 若不相等: ① key<中间值,在左半边继续查找 ② key>中间值,在右半边继续查找 算法实现 ...
  • 顺序查找 顺序查找,是一种最直观的查找方式。原理闲荡简单就是我们正常思维的查找,从给定的序列出发,依次检查序列中的每一个项目是否为我们给定的关键字。是则查找成功,否则查找失败。 bool searchByOrder...
  • 本文实例为大家分享了C语言实现顺序表的顺序查找和折半查找的具体代码,供大家参考,具体内容如下 顺序查找: #include using namespace std; int SeqSearch(int r[],int n,int k) { r[0]=k;//下标0用作哨兵存放...
  • c++实现顺序查找,折半查找

    千次阅读 2017-07-21 16:40:24
    if (EQ(key,L.elem[mid])) { cout 折半查找:元素" 的位置为:" ; break; } else if (key [mid]) { high = mid - 1; } else { low = mid + 1; } } } void PrintL(SqList &L) { int i = 0;...
  • /* 折半查找 输入一个数,查找它是这个10长数组的第几个元素 */ int main() { int arr[10]={1,5,6,8,9,12,15,17,18,20} ; int m=0,n=9;//左边界:m,右边界:n int num;//需要查找的数 cin>>num;//输入这个...
  • 只有排序之后的数据才能进行折半(二分)查找。 引用博客的一段话来理解递归如何理解递归 要理解递归,我们要退一步,了解另一个概念——「分而治之」。稍微了解程序设计的人,对这个概念应该不陌生。通俗的说,...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 6,726
精华内容 2,690
关键字:

折半查找c++

c++ 订阅