学海网 文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > 二分搜索算法

二分搜索算法

二分搜索算法 问题描述:设a[0:n-1]是一个已排好序的数组。请改写二分搜索算法,使得当搜索元素x不在数组中时,返回小于x的最大元素的位置i和大于x的最小元素位置j。当搜索元素在数组中时,i和j相同,均为x在数组中的位置。并对自己的程序进行复杂性分析。

算法设计:已知a[0:n-1]是一个已排好序的数组,可以采用折半查找(二分查找)算法。如果搜索元素在数组中,则直接返回下表即可;否则比较搜索元素x与通过二分查找所得最终元素的大小,注意边界条件,从而计算出小于x的最大元素的位置i和大于x的最小元素位置j。

代码如下:

View Code

找数:

问题描述:设n个不同的整数排好序后存于a[0:n-1]中。若存在一个下标0≤i<n,使得a[i]=i。设计一个有效算法找到这个下标。要求算法在最坏情况下的计算时间为O(logn)。

算法设计:由于题目要求算法在最坏情况下的计算时间为O(logn),故不能一个一个元素判断。数组a 中的元素各不相同而且还是排好序的,如果存在多个下标0≤i<n,使得a[i]=i,那么这几个元素在数组中是连续的。故首先应找到其中一个满足条件的元素,可以用二分查找,然后根据是连续的求出其他的满足条件的元素。另外还有种情况是数组中不存在这样的元素。

代码如下:

第1页

我要评论

相关文档

  • 实验一 二分搜索算法

    实验一 二分搜索算法 E08620311-方凯-08 计算机(3)班一. 实验目的: 实验目的: 1、 理解分治算法的概念和基本要素; 2、 理解递归的概念; 3、 掌握设计有效...

  • 第2讲_分治算法和二分搜索算法

    第2讲_分治算法和二分搜索算法_计算机软件及应用_IT/计算机_专业资料。2-1 递归法求Fibonacci数列 Fibonacci数列: 1, 1, 2, 3, 5, 8, 13… ?迭代法求Fib...

  • 二分搜索算法-三分基础-算法入门

    二分搜索算法-三分基础-算法入门_工学_高等教育_教育专区。二分搜索算法是ACM和查找算法的入门知识,三分则类比于二分可以容易理解二...

  • 编程实现二分搜索算法

    编程实现二分搜索算法_计算机软件及应用_IT/计算机_专业资料 暂无评价0人阅读0次下载举报文档 编程实现二分搜索算法_计算机软件及应用_IT/计算机_专业资料。//...

  • 二分搜索算法

    ?using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace _1._2二分搜索算法 { class Program { static void Main(...

  • 02实验二 递归与二分搜索算法

    实验二一、实验目的 递归与二分搜索算法 1.掌握分治算法的基本思想(分-治-合) 、技巧和效率分析方法; 2.分析并掌握“二分搜索问题”的递归与分治算法; 3....

  • 二分搜索算法

    //设 a[0:n-1]是已排好序的数组,请改写二分搜索算法,使得搜索元素 x 不在数组中时,返回小于 x 的最大 元素位置 i 和大于 x 的最小元素位置 j.当搜索...

  • 二分查找算法设计

    8 查找二分查找算法设计 二叉排序树及构造 平衡二叉树的查找、 平衡二叉树的查找、插入及旋转 hash表的构造及查找 表的构造及查找 8.1 二分(折半)查找 二...

  • 二分搜索算法和快速排序算法及分治策略

    实验课程:算法分析与设计 实验名称:实验二 实验目标: 1、熟悉二分搜索算法和快速排序算法; 2、初步掌握分治算法; 实验任务: 掌握分治策略的概念和基本思想。 实验...

  • 各种查找算法的性能比较测试(顺序查找、二分查找)

    关键字:顺序查找、二分查找(递归与非递归) 第一章:简介(Introduction) 1.1 算法背景 查找问题就是在给定的集合(或者是多重集,它允许多个元 素具有相同的值)...

站点地图 | 文档上传 | 侵权投诉 | 手机版
新浪认证  诚信网站  绿色网站  可信网站   非经营性网站备案
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.xuehai.net All Rights Reserved.  email
返回顶部