`
coolszy
  • 浏览: 1412533 次
  • 性别: Icon_minigender_1
  • 来自: 南京
社区版块
存档分类
最新评论

搜索算法----线性搜索、二叉搜索

阅读更多
/**
 * 线性搜索
 */
package com.szy.structure.search;

import java.util.Scanner;

public class SequentialSearch
{
	public static void main(String[] args)
	{
		int number[]={10,-2,30,22,1,2,5,4,3,20};
		Scanner scanner=new Scanner(System.in);
		System.out.println("Input the number you want to search:");
		int input=scanner.nextInt();  //不考虑输入的内容是否合法
		//线性查找
		for (int i = 0; i < number.length; i++)
		{
			if(number[i]==input)
			{
				System.out.println(input+" was found at the position of "+(i+1));
				break;
			}
		}
		System.out.println("The number you input wasn't in the array");
	}
}

 

 

/**
 * 二叉搜索
 */
package com.szy.structure.search;

import java.util.Scanner;

public class BinarySearch
{
	public static void main(String[] args)
	{
		//假设数组已经排好序,没排序好的使用排序算法排序
		int number[]={1,2,4,6,8,32,44,67,89,100,110};
		Scanner scanner=new Scanner(System.in);
		System.out.println("Input the number you want to search:");
		int input=scanner.nextInt();  //不考虑输入的内容是否合法
		
		int lowbound=0;
		int upperbound=number.length-1;
		int mid=(lowbound+upperbound)/2;
		while((input!=number[mid]&&(lowbound<=upperbound)))
		{
			if (input>number[mid])
			{
				lowbound=mid+1;
			}
			else
			{
				upperbound=mid-1;
			}
			mid=(lowbound+upperbound)/2;
		}
		if (input==number[mid])
		{
			System.out.println(input+" was found at the position of "+(mid+1));
		}
		else
		{
			System.out.println("The number you input wasn't in the array");
		}
	}
}

 

 

分享到:
评论

相关推荐

    数据结构和算法-思维导图.pdf

    - 二分查找和二叉搜索树的复杂度分析,平均时间复杂度通常为O(logn)。 - 大多数遍历操作的时间复杂度为O(n^2),比如双重循环。 - 递归操作通常具有O(n)的时间复杂度。 - 线性辅助空间复杂度,例如在进行原地排序...

    PHP-使用php开发的搜索算法-Searches.zip

    4. **二叉搜索树(Binary Search Tree, BST)**:是一种自平衡的数据结构,每个节点的左子树只包含比它小的元素,右子树包含比它大的元素。插入、删除和查找操作的时间复杂度可以达到O(log n)。 5. **Trie(字典树...

    算法-搜索- 概述.rar

    二叉搜索树是一种特殊的树,其中每个节点的左子树只包含小于当前节点的元素,右子树包含大于当前节点的元素。因此,搜索、插入和删除操作的平均时间复杂度为O(log n)。还有AVL树和红黑树等自平衡二叉搜索树,它们...

    算法-数据结构和算法-4-栈和队列.rar

    理解并熟练掌握栈和队列对于程序员来说至关重要,因为这些基础数据结构是构建复杂算法和数据结构的基础,如堆、二叉堆、哈希表、图和树等。在实际编程中,合理选择和运用数据结构可以显著提升代码效率和可读性。因此...

    图-Floyed算法-Dijkstra算法-拓扑排序算法(VC++程序)

    这个算法使用优先队列(例如二叉堆)来维护待处理的顶点,并始终保持当前已知最短路径。每次从队列中取出一个顶点,更新与其相邻且未被处理的顶点的距离。Dijkstra算法假设所有边的权重都是非负的,若存在负权重,...

    二分搜索树-二叉查找树 .docx

    二分搜索树,又称二叉查找树或有序二叉树,是一种特殊类型的二叉树,其每个节点都遵循以下规则: 1. 节点的左子树仅包含键值小于该节点的节点。 2. 节点的右子树仅包含键值大于该节点的节点。 3. 左右子树同样也是...

    C常用算法-----程序集

    4. **树算法**:如二叉搜索树、AVL树、红黑树等,它们是数据结构中的重要组成部分,常用于高效的查找、插入和删除操作。 5. **动态规划**:这是一种解决最优化问题的策略,通过将原问题分解为相互重叠的子问题来...

    数据结构与算法 -电子教案

    二叉搜索树用于快速查找,AVL树和红黑树则保证了树的平衡,提高了查找效率;B树和B+树常用于数据库索引。 6. **图算法**: 图遍历(深度优先搜索和广度优先搜索)、最短路径算法(Dijkstra算法、Floyd算法、Bellman-...

    零基础学算法--自己花钱买的资料

    8. **数据结构优化**:如堆(优先队列)、平衡二叉搜索树(AVL、红黑树等)等,这些高效的数据结构在算法实现中起到关键作用。 9. **字符串处理**:KMP算法、后缀数组、AC自动机等字符串处理算法,对于处理文本信息...

    算法-数据结构和算法-10-选择排序.rar

    - **堆排序**:选择排序的思想启发了堆排序的诞生,堆排序利用了二叉堆的数据结构,可以在O(n log n)的时间复杂度内完成排序,但仍然不是稳定的排序算法。 ### 其他排序算法对比: - **冒泡排序**:与选择排序相似...

    算法-理论基础- 查找(包含源程序).rar

    8. **图查找算法**:在图结构中,查找算法通常用于寻找路径,如深度优先搜索(DFS)和广度优先搜索(BFS)。DFS易于实现,但可能导致栈溢出;BFS则能找到最短路径。 9. **源程序分析**:压缩包中的源程序可能包含了...

    算法-数据结构知识——树的三种不同遍历算法解析.rar

    对于二叉搜索树,中序遍历的结果是有序序列,可以用于排序或验证树是否为二叉搜索树。 3. 后序遍历(Postorder Traversal): 后序遍历按照“左-右-根”的顺序进行。首先遍历左子树,接着遍历右子树,最后访问根...

    JavaScript算法源代码(例如:二叉搜索树、笛卡尔乘积、线性搜索、存储桶排序、DFS、 Kruskal算法、欧几里,等等)

    JavaScript算法源代码(例如:二叉搜索树、笛卡尔乘积、线性搜索、存储桶排序、DFS、 Kruskal算法、欧几里,等等) 链表、双链表、队列、Stack、哈希表、堆 - 最大和最小堆、优先队列、Trie、树、二叉搜索树、AVL树...

    算法程序实例(数据结构与算法-程序、素材)

    二叉树、二叉搜索树、平衡树(如AVL树和红黑树)等都是常见的树形结构。 6. **图(Graph)**:图由节点和边组成,用于表示对象之间的关系。有向图和无向图、加权图和无权重图是图的不同形式。图的常见算法包括深度...

    算法导论--教师手册

    - **二叉搜索树(Binary Search Trees)**:章节12讲解了二叉搜索树的性质和操作,以及如何平衡二叉搜索树以保持其效率。 - **红黑树(Red-Black Trees)**:章节13深入探讨了红黑树这一自平衡二叉搜索树,确保了在...

    重大-数据结构与算法-课程实验.zip

    例如,可能会要求设计一个高效的排序算法(如快速排序、归并排序),或者实现一个二叉搜索树并进行插入、删除和查找操作。 "README.md"文件通常是项目或课程的指南,包含有关实验目的、要求、评估标准和可能的参考...

    算法-第4版-完整版

    3.4.3 基于线性探测法的散列表 300 3.4.4 调整数组大小 304 3.4.5 内存使用 306 3.5 应用 312 3.5.1 我应该使用符号表的哪种实现 312 3.5.2 集合的API 313 3.5.3 字典类用例 315 3.5.4 索引类...

Global site tag (gtag.js) - Google Analytics