`
fehly
  • 浏览: 248711 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

二分搜索技术

阅读更多

             二分搜索算法是运用分治策略的典型例子。

             给定已排好序的n个元素a[0:n-1],现在在这个n个元素中找出一个特定元素x。

             首先较易想到的是用顺序搜索方法,逐个比较a[0:n-1]中元素,直至找出元素x或搜索遍整个数组后确定x不在其中。这个方法没有很好地利用n个元素已排好序这个条件,因此在最坏情况下,顺序搜索方法需要O(n)次比较。

             二分搜索方法充分利用了元素间的次序关系,采用分治策略,可在最坏情况下用O(logn)时间完成搜索任务.

             二分搜索算法的基本思想是将n个元素分成个数大致相同的两半,取a[n/2]与x进行比较。如果x=a[n/2],则找到x,算法终止。如果x<a[n/2],则只要在数组a的左半部继续搜索x。如果x>a[n/2],则只要在数组a的右半部继续搜索x

具体算法demo如下:

 

package Recursive;
/**
 * 递归与分治策略-二分搜索
 */
public class er_fen_Search
{
	public static int binarySearch(int []a,int x)
	{
		//在a[0]<=a[1]<=...<=a[n-1]中搜索x
		//找到x时返回其在数组中的位置,否则返回-1
		int left=0;int right=a.length-1;
		while(left<=right)
		{
			int middle=(left+right)/2;
			if(x==a[middle]) return middle;
			if(x>a[middle]) left=middle+1;
			else right=middle-1;
		}
		return -1;//为找到
	}
	public static void main(String[] args)
	{
		int a[] ={1,2,3,4,5,6,7,8,9,10};
		int find = er_fen_Search.binarySearch(a, 2);
		System.out.println(find >= 0 ? "找到数值索引" + find : "找不到数值" );
	}
}

  查找2在数组的位置 

  运行结果为:

找到数值索引1

 

 

 

              容易看出,每执行一次算法的while循环,待搜索数组的大小减小一半,因此在最坏情况下,while循环被执行了O(logn)次,循环体内运算需要O(1)时间,因此整个算法在最坏情况下的计算时间复杂性为O(logn)。

              

分享到:
评论

相关推荐

    合并排序算法和二分搜索技术算法的实现实验报告.doc

    合并排序算法和二分搜索技术算法的实现实验报告.doc

    推荐多个详细教程讲解二分搜索技术以及实现方法

    2. **CSDN 文库** 的“二分搜索技术-算法课程设计 PPT 资源”提供了PPT形式的详细讲解,有助于视觉学习者理解。 3. **知乎** 上的“图文并茂带你入门二分查找算法”文章,结合实例和图形,帮助读者深入理解二分搜索...

    实验1二分搜索技术-v2.pdf

    实验1二分搜索技术-v2.pdf

    二分查找算法流程图流程图举例

    二分查找算法是一种在有序数组中查找特定元素的搜索算法。搜索过程从数组的中间元素开始,如果中间元素正好是目标值,则搜索结束;如果目标值大于或小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且...

    java二分搜索法程序,分行显示

    本文将详细解析标题“java二分搜索法程序,分行显示”所涉及的Java编程技术,包括二分搜索法的原理、实现以及如何结合数据结构进行文字处理。 首先,我们来了解**二分搜索法**(Binary Search)。它是一种在有序...

    二分查找算法

    介绍二分查找的基本概念以及二分查找的思路与过程

    C++实现的二分搜索

    总的来说,这个C++实现的二分搜索项目展示了如何在实际问题中运用算法和文件处理技术。它不仅涉及数据结构(如数组)和算法(二分搜索),还涵盖了输入输出操作,这些都是软件开发中的重要技能。通过学习和分析这样...

    二分搜索算法及其源代码

    二分搜索算法是一种高效、基于比较的搜索技术,它在有序数据集合中寻找目标值。这个算法的核心思想是不断缩小搜索范围,通过每次迭代将搜索区间减半,从而快速定位到目标元素。二分搜索算法在计算机科学和编程中有着...

    算法原理与实践课件6_排序和二分搜索_Help!_algorithmtheory_movingp1q_

    《算法原理与实践课件6_排序和二分搜索》是针对计算机科学中核心概念——排序算法和二分搜索技术的深入讲解。这份文档旨在帮助读者理解和掌握C++编程语言中的算法实现。在这个主题中,我们将探讨以下几个重要的知识...

    二分搜索_快速排序_背包问题

    二分搜索算法是一种高效的搜索技术,适用于已排序的数组。其核心思想是通过不断将搜索区间减半的方式来减少搜索范围,从而提高搜索效率。具体步骤如下: 1. 计算当前搜索区间的中间位置 `mid`。 2. 比较目标值 `x` ...

    erfensousuo.rar_二分搜索

    二分搜索,也被称为折半搜索,是一种在有序数组中查找特定元素的搜索算法。它的基本思想是将数组分成两半,然后比较中间元素与目标值,根据比较结果决定是在左半部分还是右半部分继续搜索,直到找到目标元素或者搜索...

    一种双线性分段二分网格搜索SVM最优参数方法.pdf

    本文提出了一种双线性分段二分网格搜索方法来确定 SVM 模型的最优参数。该方法首先在初始搜索范围内,以等间隔固定取样值,对惩罚因子进行采样,分别计算这些取样点的 SVM 的交叉验证正确率,并寻找出满足交叉验证...

    flash as3 二分查找动画演示

    在这个"flash as3 二分查找动画演示"项目中,我们看到的是一个用Flash AS3实现的二分查找算法的可视化教程。 二分查找(Binary Search)是计算机科学中一种高效的数据检索方法,适用于已排序的数组或列表。它的基本...

    二分搜索和压缩感知在激光超声内部缺陷快速检测技术的应用.docx

    本文探讨了二分搜索和压缩感知技术在激光超声内部缺陷快速检测中的应用,旨在解决传统检测技术耗时过长的问题。激光超声无损检测技术结合了超声波探伤的精确性和光学系统的灵活性,适用于检测结构内部的缺陷,如在...

    java二分查找实现

    Java 二分查找是搜索有序数组中某个元素的最常用算法之一。它的实现原理是将数组分成两个部分,然后在其中一个部分继续进行搜索,直到找到目标元素或确定目标元素不存在。下面将详细介绍 Java 二分查找的实现技术。 ...

    算法设计---作业---实验1

    1. 实现二分搜索技术 2. 实现合并排序 3. 实现快速排序 其中,我们选择了前两个实验内容进行实现。 三、实验实现 二分搜索 二分搜索是一种经典的搜索算法,它可以在有序数组中快速查找某个元素。其核心思想是将...

    二分查找和hash表的实现

    二分查找,也称为折半查找,是一种在有序数组中查找特定元素的搜索算法。它的核心思想是通过比较目标值与数组中间元素的大小关系,不断缩小搜索范围。以下是二分查找的基本步骤: 1. 计算数组的中间索引。 2. 如果...

    搜索引擎技术分享

    #### 二、搜索引擎的组成部分与工作原理 搜索引擎通常由以下几个关键部分组成: ##### 2.1 搜索器(Crawler) 负责在网络上爬取网页信息,也被称为“蜘蛛”或“机器人”。搜索器会根据预设的规则访问互联网上的...

    互联网搜索技术PPT

    互联网搜索技术是信息技术领域中的一个重要分支,它涉及多种技术和算法,旨在高效地处理海量数据,为用户提供准确、快速的查询结果。本篇内容主要涵盖了搜索技术的概论、搜索引擎技术、系统架构、性能优化以及分布式...

    VB 二分查找

    总结,VB中的二分查找是一种高效的搜索技术,尤其适合处理大量有序数据。通过理解其工作原理并正确实现,开发者可以充分利用这种算法来提升程序性能。在实际编程中,结合具体的业务需求和数据特点,选择最适合的查找...

Global site tag (gtag.js) - Google Analytics