精华内容
下载资源
问答
  • 折半查找习题解答

    2011-11-09 16:40:00
    1、本节的折半查找算法有一个特点:如果待查找的元素在数组中有多个则返回其中任意一个,以本节定义的数组int a[8] = { 1, 2, 2, 2, 5, 6, 8, 9 };为例,如果调用binarysearch(2)则返回3,即a[3],而有些场合下要求...

    1、本节的折半查找算法有一个特点:如果待查找的元素在数组中有多个则返回其中任意一个,以本节定义的数组int a[8] = { 1, 2, 2, 2, 5, 6, 8, 9 };为例,如果调用binarysearch(2)则返回3,即a[3],而有些场合下要求这样的查找返回a[1],也就是说,如果待查找的元素在数组中有多个则返回第一个。请修改折半查找算法实现这一特性。

    //By LYLtim
    
    #include<stdio.h>
    
    #define LEN 8
    int a[LEN] = { 1, 2, 2, 2, 5, 6, 8, 9 };
    
    int Search(int k)
    {
    	int start = 0, end = LEN -1;
    	while (start <= end) {
    		int mid = (start + end) >> 1;
    		if (k < a[mid])
    		    end = mid -1;
    		else if (k > a[mid])
    		    start = mid +1;
    		else {
    			while (a[mid-1] == a[mid]) mid -= 1;
    			return mid;
    		}
    	}
    	return -1;
    }
    		
    
    int main(void)
    {
    	printf("%d\n",Search(2));
    	return 0;
    }
    

     

    2、编写一个函数double mysqrt(double y);y的正平方根,参数y是正实数。我们用折半查找来找这个平方根,在从0到y之间必定有一个取值是y的平方根,如果我们查找的数xy的平方根小,则x2<y,如果我们查找的数xy的平方根大,则x2>y,我们可以据此缩小查找范围,当我们查找的数足够准确时(比如满足|x2-y|<0.001),就可以认为找到了y的平方根。

    //By LYLtim
    double mysqrt(double y)
    {
    	double l = 0, r = y, x;
    	while (r - l > 0.000001) {
    		x = (l + r) / 2;
    		if (x * x > y) r = x;
    		else l = x;
    	}
    	return (l + r) / 2;
    }
    

     

    3、编写一个函数double mypow(double x, int n);xn次方,参数n是正整数。最简单的算法是:

    double product = 1;
    for (i = 0; i < n; i++)
    	product *= x;

    这个算法的时间复杂度是Θ(n)。其实有更好的办法,比如mypow(x, 8),第一次循环算出x·x=x2,第二次循环算出x2·x2=x4,第三次循环算出4·x4=x8。这样只需要三次循环,时间复杂度是Θ(lgn)。思考一下如果n不是2的整数次幂应该怎么处理。

     1 // 递归版 By LYLtim
     2 double mypow(double x, int n)
     3 {
     4     if (n == 1) return x;
     5     else {
     6         double tmp = mypow(x, n >> 1);
     7         tmp *= tmp;
     8         if (n & 1)
     9             return tmp * x;
    10         else
    11             return tmp;
    12     }
    13 }
     1 // 非递归版 By LYLtim 
     2 double mypow(double x, int n){
     3     double s = 1;
     4     while (n) {
     5         if (n & 1) s *= x;
     6         x *= x;
     7         n >>= 1;
     8     }
     9     return s;
    10 }

     

    转载于:https://www.cnblogs.com/LYLtim/archive/2011/11/09/2243081.html

    展开全文
  • 我建议还是看吧,不长) [题目分析] 给出的 ... CAN总线学习记录之四:位定时与同步 一.位定时 1.1 比特率和波特率 1)位速率:又叫做比特率(bit rata).信息传输率,表示的是单位时间内,总线上传输的信息量,即每秒...

    MongoDB管理工具的插件系统

    MongoDB管理工具  MongoCola的开发已经进入第三个年头了. 官方对于C#驱动的投入不够导致了很多东西都必须自己实现,但是不管怎么样,工具现在已经很强大了. 最近准备着手插件系统的开发,简 ...

    js jquery 等的地址

    jquery在线地址(jquery地址):http://code.jquery.com/jquery-latest.js js人脉图(关系图)插件: http://js.cytoscape.org/

    通过使用CyclicBarrier来计算Matrix中最大的值

    import java.util.Random; import java.util.concurrent.CyclicBarrier; import java.util.concurrent.Exec ...

    HDU2094(产生冠军)题解

    HDU2094(产生冠军)题解 以防万一,题目原文和链接均附在文末.那么先是题目分析: [一句话题意] 根据给定现有比赛结果推断分析冠军.(这描述...我建议还是看题吧,题不长) [题目分析] 给出的 ...

    CAN总线学习记录之四:位定时与同步

    一.位定时 1.1 比特率和波特率 1)位速率:又叫做比特率(bit rata).信息传输率,表示的是单位时间内,总线上传输的信息量,即每秒能够传输的二进制位的数量,单位是bit per second ...

    【翻译】JavaScript中5个值得被广泛使用的数组方法

    展开全文
  • 数据结构知识点练习题——折半查找 请实现有重复数字的有序数组的二分查找。 输出在数组中第一个大于等于查找值的位置,如果数组中不存在这样的数,则输出数组长度加一 输入: 5,4,[1,2,4,4,5] 输出: 3 折半查找...

    数据结构知识点练习题——折半查找

    请实现有重复数字的有序数组的二分查找。
    输出在数组中第一个大于等于查找值的位置,如果数组中不存在这样的数,则输出数组长度加一

    输入:
    5,4,[1,2,4,4,5]
    输出:
    3

    折半查找原理:(自己查百度吧)
    好了,说代码:

    在这里插入代码片        
    		//验证数据
    		//2,3,4,4,4,7,7,8,10,10,11,12,13,14,15,15,17,18,19,23,24,24,24,24,25,26,26,26,27,27,28,
            //29,29,30,33,36,38,38,40,40,41,43,43,43,44,46,46,47,51,52,52,53,54,56,57,57,57,58,58,61,61,61,62,
            //64,64,66,66,67,67,67,70,72,74,74,74,75,75,78,78,78,79,79,80,83,83,83,83,84,84,86,88,89,89,90,91,91,92,93,93,96
            var n = prompt('请输入数组长度:');
            var v = prompt('请输入要查找的数字:');
            var a = prompt('请输入要查找的数组:');
            a = a.split(',');
            var height = parseInt(n)
            var low = 0;
            v = parseInt(v)
            //递归查找不适合查询太大的数组
            //102ms
            // 运行时间
            //18196KB
            // 占用内存
            function getMax(arr, low, height, k) {
                if (low > height || arr[height] < k) {
                    return height + 1
                } else {
                    var mid = Math.floor((height + low) / 2);
                    if (arr[mid] >= k && arr[mid - 1] < k) {
                        console.log(mid);
                        return mid + 1;
                    } else if (arr[mid] >= k && arr[mid - 1] >= k) {
                        console.log(mid);
                        return getMax(arr, low, mid - 1, k)
                    } else {
                        console.log(mid);
                        return getMax(arr, mid + 1, height, k)
                    }
                }
    
            }
            console.log(getMax(a, low, height, v));
            //非递归方法 
            //106ms
            //运行时间
            //17664KB
            //占用内存
            function getMax_(arr, n, v) {
                if (arr[n - 1] < v) {
                    return n + 1
                }
                let height = n;
                let low = 0
                while (low <= height) {
                    var mid = Math.floor((height + low) / 2);
                    if (arr[mid] >= v) {
                        if (arr[mid - 1] && arr[mid - 1] >= v) {
                            height = mid - 1
                        } else {
                            return mid + 1
                        }
                    } else {
                        low = mid + 1
                    }
                }
            }
            console.log(getMax_(a, height, v));
    
    

    总结:可以用普通的非递归方式编写,容易理解,代码可读性也高;用递归方式编写,理解难度有一点,最主要是这样可以让别人问你(hhh)

    展开全文
  • 折半查找法 谭浩强习题

    千次阅读 2018-11-14 21:56:54
    #include&lt;stdio.h&gt; #include&lt;stdlib.h&gt; int main() { int a[15], x; puts("请按从大到小输入15个数:"); for (int i = 0; i &lt; 15;... for (lo...
  • C语言习题 折半查找

    千次阅读 2017-08-11 14:04:59
    2413: C语言习题 折半查找 Time Limit: 1 Sec Memory Limit: 128 MB Submit: 1829 Solved: 687 [Submit][Status][Web Board] Description 有n个数(n 要求: 编写两个函数input和binbearch分别实现...
  • Problem B: C语言习题 折半查找Description有n个数(n&lt;20),已按从大到小顺序存放在一个数组中,输入一个数,要求用折半查找法找出该数是数组中的第几个元素的值。如果不在数组中输出0。要求: 编写两个函数...
  • 折半查找

    千次阅读 2014-03-10 17:54:41
    Problem H: C语言习题 折半查找 Time Limit: 1 Sec Memory Limit: 128 MB Submit: 478 Solved: 170 [Submit][Status][Web Board] Description 有n个数(n 要求: 编写两个函数input和binbearch分别实现数组数据...
  • 折半查找

    千次阅读 多人点赞 2020-03-19 20:43:24
    文章目录折半查找法摘要概述引申解题步骤算法代码实现 折半查找法 摘要 折半查找法是效率较高的一种查找方法。假设有已经按照从小到大的顺序排列好的五个整数a0~a4,要查找的数是X,其基本思想是: 设查找数据的范围...
  • 谭浩强C++课后习题21——折半查找 题目描述:有15个数字由大到小的顺序存放在一个数组中,输入一个数,要求用折半查找法找出该数是数组中第几个元素的值。如果该数不在数组中,则打印出“无此数”。 算法思路:从一...
  • 这是一个关于数组查找方式的练习,供大家学习交流~~
  • C语言习题折半查找

    千次阅读 2015-12-27 16:56:30
    要求: 编写两个函数input和binbearch分别实现数组数据的输入和元素的查找。 Input 第一行数组元素的个数n 第二行n个数组元素的值 第三行要查找的值 Output 查找的值在数组中的位置 Sample Input 10 10 9 8 7 6...
  • Problem A: C语言习题 折半查找Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 3306 Solved: 1441[Submit][Status][Web Board]Description有n个数(n&lt;20),已按从大到小顺序存放在一个数组中,输入一...
  • 二分查找也常被称为二分法或者折半查找,每次查找时通过将待查找区间分成两部分并只取一部分继续查找,将查找的复杂度大大减少。对于一个长度为 O(n) 的数组,二分查找的时间复杂度为 O(log n)。
  • YTU 2413 C语言习题折半查找

    千次阅读 2019-04-08 12:12:41
    =1000000),这n个数已按从大到小顺序存放在一个数组中,然后有T次查询,每次输入一个数,要求用折半查找法找出该数在数组中第一次出现的位置。如果不在数组中输出0。 输入 第一行数组元素的个数n 第二行n个数组...
  • XYNUOJ 习题6-9 折半查找

    千次阅读 2018-01-31 19:07:12
    习题6-9 折半查找 时间限制: 1 Sec 内存限制: 12 MB [提交][状态][讨论版] 题目描述 有10个整数已按从小到大的顺序排好序,存储在一个数组中,再输入一个数,要求用折半查找法找出该数是数组中的第几个...
  • 1095 习题6-9 折半查找

    2018-03-27 22:15:49
    题目描述有10个整数已按从小到大的顺序排好序,存储在一个数组中,再输入一个数,要求用折半查找法找出该数是数组中的第几个元素(输出该元素的下标即可)。如果该数不在数组中,则输出"Not exist!"输入...
  • 主要介绍了C语言数据结构之 折半查找实例详解的相关资料,需要的朋友可以参考下
  • 例如:对静态查找表先冒泡排序为{5,13,19,21,37,56,64,75,80,88,92},再采用折半查找算法查找37。 #include using namespace std; int main() { int arr[] = { 5,13,19,21,37,56,64,75,80,88,92 }; int m = sizeof...
  • oj2413:C语言习题 折半查找

    千次阅读 2017-04-26 16:50:49
    问题描述:有n个数(n 要求: 编写两个函数input和binbearch分别实现数组数据的输入和元素的查找。...问题描述:有n个数(n),已按从大到小顺序存放在一个数组中,输入一个数,要求用折半查找法找出该数是
  • import java.util.*;//声明的类库class ArrayTest_5{/*... 有序的数组 并涉及查找的时候可以使用折半查找明确2. 数组一旦初始化之后 内容不可以被改变 但是要是想放 但是获取位置是可以的*/public static void main(S
  • Java 折半查找

    2016-12-15 20:53:49
    * 折半查找:可以用来比较快速的查找某个值的索引位置  * 1.先规定一个最小的索引min=0和最大的索引max=arr.length-1 * 2.取mid=(min+max)/2  * 3.中间索引的值与value比较  * 大了:max=mid-1;  * 小了...
  • 【数据结构】折半查找及其二叉判定树画法

    万次阅读 多人点赞 2019-09-25 23:55:40
    折半查找又叫二分查找,是数据结构中一种很重要的查找方式。 其特点有以下几个: 只能对有序的顺序表进行查找。 是一种静态查找。 查找的平均时间复杂度为o(log2n)。 成功平均查找长度ASL约log2(n+1)-1。 ...

空空如也

空空如也

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

折半查找练习题