精华内容
下载资源
问答
  • 编写程序数据序列采用二分查找法和顺序查找法查找元素的下标,要求使用类模板实现(其中二分法查找算法要求用递归实现,给定数据序列有序)。
  • 问题的提出:编写程序数据序列采用二分查找法和顺序查找法查找元素的下标,要求使用类模板实现(其中二分法查找算法要求用递归实现,给定数据序列有序)。

    问题的提出:编写程序对数据序列采用二分查找法和顺序查找法查找元素的下标,要求使用类模板实现(其中二分法查找算法要求用递归实现,给定数据序列有序)。

    代码:

    // test12_1.cpp : 定义控制台应用程序的入口点。
    //利用二分查找和顺序查找元素的下标,类模板实现且二分类查找算法要求利用递归算法
    
    #include "stdafx.h"
    #include <iostream>
    
    using namespace std;
    
    //const int Max=100;
    
    template<typename T>
    class Search
    {
    private:
    	T *A;
    	int n;
    public:
    	Search(){}
    	Search(T *a, int n)
    	{
    		A=a;
    		this->n=n;
    	}
    	void disp();
    	int seek(T *a, int n, T e);
    	int seek1(T *a, int start, int end, T e);
    };
    
    template<typename T>
    void Search<T>::disp()
    {
    	for(int i=0; i<n; i++)
    	{
    		cout<<A[i]<<" ";
    	}
    	cout<<endl;
    }
    
    template<typename T>
    int Search<T>::seek(T *a, int n, T e)
    {
    	//顺序查找法
    	for(int i=0; i<n; i++)
    	{
    		if(a[i]==e)
    		{
    			return (i+1);
    		}
    	}
    	return -1;
    }
    
    template<typename T>
    int Search<T>::seek1(T *a, int start, int end, T e)
    {
    	//二分查找法
    	int mid;
    	mid=(start+end)/2;
    	if(e>a[mid])
    	{
    		return seek1(a,mid+1,end,e);
    	}
    	else if(e<a[mid])
    	{
    		return seek1(a,start,mid-1,e);
    	}
    	else
    	{
    		return mid;
    	}
    	return -1;
    }
    
    
    int _tmain(int argc, _TCHAR* argv[])
    {
    	//二分查找法
    	int a[]={1,2,3,4,5,6,7,8,9,10};
    	Search<int> Num(a,10);
    	cout<<"原始数据集: ";
    	Num.disp();
    	cout<<"请输入你要查找的元素:";
    	int e;
    	cin>>e;
    	int p1=Num.seek1(a,0,9,e);
    	if(p1==-1)
    	{
    		cout<<"你输入的元素不存在!"<<endl;
    	}
    	else
    	{
    		cout<<"元素"<<e<<"在第"<<p1+1<<"个位置"<<endl;
    	}
    
    	//顺序查找法
    	char b[]="bdaolfjmsx";
    	Search<char> Character(b,10);
    	cout<<"原始数据集: ";
    	Character.disp();
    	cout<<"请输入你要查找的元素:";
    	char c;
    	cin>>c;
    	int p = Character.seek(b,10,c);
    	if(p==-1)
    	{
    		cout<<"你输入的元素不存在!"<<endl;
    	}
    	else
    	{
    		cout<<"元素"<<c<<"在第"<<p<<"个位置"<<endl;
    	}
    
    	system("pause");
    	return 0;
    }
    
    结果:



    展开全文
  • 顺序查找:对表中的元素排序无要求,但如果表中各个元素的查找概率并不相等,则应先元素的查找概率进行排序,使表中元素的查找概率由小到大重新排列,以便... /** * 顺序查找法 * @param $val 要查找的值 */ funct...

    顺序查找:对表中的元素排序无要求,但如果表中各个元素的查找概率并不相等,则应先对元素的查找概率进行排序,使表中元素的查找概率由小到大重新排列,以便提高查找概率。

    二分法查找:折半查找的效率比顺序查找高,但折半查找只适用于有序表,且限于顺序存储结构(对链式存储无效)。


    /**
    * 顺序查找法
    * @param $val 要查找的值
    */
    function query_search($array,$val)
    {
    foreach ($array as $k => $v)
    {
    if($v == $val)
    {
    return $k ;
    }
    }

    return -1 ;
    }

    /**
    * 顺序查找法
    * @param $val 要查找的值 $arr 数据源 $low 其实位置 $top 数组大小
    */
    function bin_search($arr,$low,$top,$val)
    {
    if ($low <= $top) {
    $mid = floor(($low + $top) / 2);
    if ($arr[$mid] == $val) {
    return $mid;
    } elseif ($arr[$mid] < $target) {
    return bin_search($arr, $mid + 1, $top, $target);
    } else {
    return bin_search($arr, $low, $top - 1, $target);
    }
    } else {
    return -1;
    }
    }
    // 查找的源数组
    $array = array(1,2,4,7,5,6,3,8);

    $n = query_search($array,2);
    echo "顺序查找位置->".$n."<br>";
    sort($array);
    $num = bin_search($array,0,count($array)-1,2);
    echo "二分查找位置->".$num;

    转载于:https://www.cnblogs.com/yelons/p/6524722.html

    展开全文
  • 摘要:php查找数组元素有内置的函数array_searchin_array,顺序查找对数组排序没有要求,二分查找法要求数组必须是一个有序数组!1.顺序查找function sequence_search...php查找数组元素有内置的函数array_search...

    摘要:php查找数组元素有内置的函数array_search和in_array,顺序查找对数组排序没有要求,二分查找法要求数组必须是一个有序数组!1.顺序查找function sequence_search...

    php查找数组元素有内置的函数array_search和in_array,顺序查找对数组排序没有要求,二分查找法要求数组必须是一个有序数组!

    1.顺序查找function sequence_search($arr, $k){

    foreach($arr as $key=>$val){

    if($val==$k){

    return $key;

    }

    }

    return -1;

    }

    2.二分查找

    思路分析:找到数组中间数,然后与要查找的数比较,如果要查找的数大于中间数,则说明要向后查找,否则向前查找,如果相等则说明已找到。function binary_search($arr,$val,$left,$right){

    if($left > $right){

    return -1;

    }

    $middle = round(($left+$right)/2);

    if($arr[$middle]>$val){

    return binary_search($arr, $val, $left, $middle-1);

    }elseif($arr[$middle]

    return binary_search($arr, $val, $middle+1, $right);

    }else{

    return $middle;

    }

    }

    //定义被查找的数组(有序数组)

    $arr = array(-3,-1,0,1,3,5,7);

    //要查找的值

    $val = 5;

    echo binary_search($arr, $val, 0, count($arr)-1);

    展开全文
  • 分查找法

    2020-05-26 17:04:41
    分查找对数据结构有一定的要求,它的前提是数据是有序数列(递增或递减)。 查找过程是: 1.先找到数列的中点,将数据分为大于中点值小于中点值得2个子数列。 2.对比查找值,缩小查找范围到其中一个子数列。 3.取子...

    二分查找对数据结构有一定的要求,它的前提是数据是有序数列(递增或递减)。

    查找过程是:
    1.先找到数列的中点,将数据分为大于中点值和小于中点值得2个子数列。
    2.对比查找值,缩小查找范围到其中一个子数列。
    3.取子数列中点,重复1、2步骤,直到找到目标值。

    例子:
    有1、2、3、4、5、6、7、8、9这10个数,查找其中的7。
    查找过程如下:
    在这里插入图片描述
    由图可看出,找到7二分查找用了3次,而顺序查找需要7次。
    如果数列中每个数字查找一次:
    顺序查找平均需要(1+2+3+4+5+6+7+8+9) / 9 = 5次;
    二分查找平均需要(4+3+2+3+1+4+3+2+3) / 9 = 2.78次;

    展开全文
  • 折半查找,也称二分查找,在某些情况下相比于顺序查找,使用折半查找算法的效率更高。但是该算法的使用的前提是静态查找表中的数据必须是有序的。 折半查找算法 静态查找表{5,13,19,21,37,56,64,75,80,88,92}采用...
  • 前面我们分别列出了递增查找法和分查找法,各有优缺点。递增适用范围广,对数组元素顺序没有要求,但效率较低;而二分法运算效率高,但数组元素的排列有要求需要从小到大排序好。因此我们可以将两种算法组合到一...
  • 1. 作用要求当我们要从一个序列中查找一个元素的时候,二分查找是一种非常快速的查找算法,二分查找又叫折半查找。它要查找的序列有两个要求,一是该序列必须是有序的(即该序列中的所有元素都是按照大小关系排好...
  • 分查找只适用顺序存储结构。为保持表的有vb.net教程序性,在顺序结构里插入删除都必须移动大量的结点。因此,二分查找特别适用于那种一经建立就很少改动、而又经常需要查找的线性表。 那些查找少而又经常需要...
  • 分查找和递归

    2019-06-29 07:30:09
    分查找法一组有序的数字中进行查找,传递相应的数据,进行比较查找到与原数据相同的数据,查找到了返回对应的数组下标,没有找到返回-1; 如下示例,其中有序数组中, 是按照从小到大的顺序排列的。(再次感谢...
  • C 二分查找算法.rar

    2019-07-10 09:23:17
    C 二分查找算法源码实例,编写程序数据序列采用二分查找法和顺序查找法查找元素的下标,要求使用类模板实现(其中二分法查找算法要求用递归实现,给定数据序列有序)。
  • 分查找

    2018-08-12 12:04:28
    列的查找主要分为顺序查找和分查找,其中顺序查找分为从头查找从尾查找,为了提高查找的效率便引入了监督元技术,以空间来换取时间提高查找的效率,但总的来说,二分查找具有更高的效率,下面主要来介绍二...
  • 如果把这些词全部读入内存,然后用二折半查找其实很简单,现在问题是由于在手持设备上读取,不能全部读入内存再查找。如果不用二分法非常慢。 但是如果用了二分法,实时定位困扰我很久,一直无法解决。因为加入...
  • 分查找(基于有序数组)

    千次阅读 2018-09-01 17:01:49
    1、基本思想 2、算法实现 3、基于二分查找的有序符号表 4、性能分析 ...二分查找法:将被查找的键子数组的中间键比较。如果被查找的键小于中间键,就在左子数组中继续查找,如果大于就在右子数组中继...
  • 查找

    2015-02-13 21:35:52
    分查找法对顺序表的查找方法,例如有一个数组int a[]={7,8,23,45,67,69,76,89,101,111}; 首先设两个变量lowhigh,分别记录二分查找的数组范围,然后用(low+high)/2求出mid,数组个数为奇数偶数都一样。 用我们...
  • C 语言版 第 9 章 查找 计算机与信息工程学院 于江德 复习提要 查 找 方 法 比较式 查找法 计算式 查找法 基于 树 的 查找法 基于 线性表 的查找法 分块或索引顺序表查找法 折半或二分查找法 顺序查找法 存储结构 ...
  • 3. 用顺序查找法在长度为n的线性表中进行查找,在等概率情况下,查找成功的平均比较次数是 。 4. 二分查找算法描述如下: intSearch_Bin(SST ST, KT key) { low=1 ; high=ST. length; while(low) { mid=(low+high)...
  • 折半查找

    2020-07-20 17:40:21
    (1)顺序查找 (2)折半查找 (1)顺序查找 思路:将所要查询的数据已经存在的所有数据进行依次比对,如果相同则找到 (2)折半查找 提前:必须是有序(升序还是降序)的数据进行查询。否则不能进行折半查找!...
  • 浏览题阅览题 会考复习题 学校_姓名_班级_考号_ 评卷人 得分 一选择题 1用对分查找法从数列367101216253075中找到数据10的查找次数是 A2 B3 C4 D7 答案C 解析 2有一组数据为2355778利用顺序查找和对分查找查找5时则...
  • 浏览题阅览题 会考 复习题 学校_姓名_班级_考号_ 评卷人 得分 一选择题 1用对分查找法从数列367101216253075 中找到数据10 的查找次 数是 A 2 B3 C4 D7 答案C 解析 2 有一组数据为2355778利用顺序查找和对分查找查找...
  • 数组的排序和查找

    2012-06-17 23:34:54
    所谓排序就是一组数据,按照某个顺序排列的过程 排序2大类: 内部排序 交换式排序 1 ,冒泡 快速体验: $arr = array (0, 5, - 1 ); //从小到大排 $temp = 0; for($i = 0; $i ( $...
  • 复习顺序查找分查找分块查找的基本算法及适用场合 2) 掌握哈希查找的基本方法及适用场合并能在解决实际问题时灵活应用 3) 巩固在散列查找时解决冲突的方法及特点 2实验内容 1) 哈希表查找的实现用线性探测解决...
  • 二分法与二叉查找

    2020-05-26 14:28:06
    分查找法一个有序序列进行一分为二的检索,每次查找范围缩小一半,直到找到所需的数或者查找范围不存在; 问题描述:一个有序序列检索一个输入的数,若该数存在则返回下标,否则返回1; 问题分析:这种问题...
  • 顺序遍历数组,将当前元素与目标值的差值作为target,针对target在数组中进行二分查找,时间复杂度为O(nlogn) 二分查找 划分:原数组进行划分,当划分得到一个元素时,可以直接进行比较 求解:targetmid进行...
  • 问题描述 在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每...也可以一维数组进行顺序查找二维数组进行二分查找。(复杂度O(n*log(m))) 也可以一维数组进行2次二分查找...
  • 在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增...2. 方法1进行优化,每行都是已排序的,则可以针对每一行都使用二分查找法,时间复杂度O(nlogn) ...
  • 在之前的写的排序算法里面可以用二分搜索的方式进行优化,这篇博客就暂且先介绍一下二分...(3)要求输入一个职工号,用 二分查找(折半查找)找出该职工的姓名。从主函数输入要查找的职工号,输出该职工姓名。 在这里插
  • 对于 MySQL 数据库而言,数据是存储在文件里的,而为了...数组要求插入的时候保证有序,这样查找的时候可以利用二分查找法达到O(log(N))的时间复杂度,范围查询支持也很好,但是插入的时候如果不是在数组尾部,就...
  • 插入排序分为两种,一种是直接插入排序,一种是二分插入排序。 首先直接插入排序的基本思想是将序列分为排序好的部分待...而二分插入排序则是直接插入排序比较过程的一个优化,即从顺序比较变成了二分查找比较。
  • 本大作业内容含:一个学生成绩表实现添加、修改、删除排序查找的功能 ...(2)排序(如冒泡,其他快速算法)查找(如顺序查找,二分查找)写出算法描述;(3)排序按分数由高到低,查找按姓名;

空空如也

空空如也

1 2 3 4 5 ... 13
收藏数 252
精华内容 100
关键字:

对分查找法和顺序查找法