`
myclover
  • 浏览: 195062 次
  • 性别: Icon_minigender_1
  • 来自: 成都
社区版块
存档分类
最新评论

实现二叉查找的两种方法

    博客分类:
  • java
阅读更多
在群里经常看到很多网友面试回来说又考了二叉查找,但是搞不懂咋个实现,看来这个查找确实是面试中出现的频率比较高的,所以就此把这方法实现一下,希望对需要帮助的朋友有所帮助,具体实现如下代码所示:
package com.myclover.utils.search;

public class SearchUtils {
	
	
	/**
	 * 功能描述:线性查找指定数组中的目标数据
	 * @param array 指定的数组
	 * @param data  目标数据
	 * @return  返回值:返回目标数据在指定数组中的索引值,如果没找到,则返回-1
	 */
	public static int linearSearch(int[] array , int data){
		for(int i = 0 ; i < array.length ; i++){
			if(data == array[i]){
				return i;
			}
		}
		return -1;
	}
	
	/**
	 * 功能描述:二分查找指定数组中的目标数据(非递归)
	 * @param array  指定的数组
	 * @param data   目标数据
	 * @return  返回值:返回目标数据在指定数组中的索引值,如果没找到,则返回-1
	 */
	public static int binarySearch(int[] array , int data){
		int low = 0;
		int high = array.length - 1;
		int mid = -1;
		if(data < array[low] || data > array[high] ||low > high){
			return -1;
		}
		while(low <= high){
			mid = (low + high) >>> 1; //相当于除以2
			if(data < array[mid]){
				high = mid - 1;
			}else if(data > array[mid]){
				low = mid + 1;
			}else{
				return mid;
			}
		}
		return -1;
	}

	/**
	 * 功能描述:二分查找指定数组中的目标数据(递归)
	 * @param array 指定的数组
	 * @param low   数组的开始索引
	 * @param high  数组的结束索引
	 * @param data  目标数据
	 * @return  返回值:返回目标数据在指定数组中的索引值,如果没找到,则返回-1
	 */
	public static int binarySearch(int[] array , int low , int high , int data){
		if(high > array.length - 1 || low < 0 || data < array[low] || data > array[high] ||low > high){
			return -1;
		}
		int mid = (low + high) >>> 1; //相当于除以2
		if(data < array[mid]){
			return binarySearch(array , low , mid - 1 , data);
		}else if(data > array[mid]){
			return binarySearch(array , mid + 1 , high , data);
		}else{
			return mid;
		}
	}
	
}


分享到:
评论

相关推荐

    二叉查找树C++实现

    二叉查找树(Binary Search Tree, BST)是一种基础但非常重要的数据结构,它在计算机科学中扮演着核心角色,尤其是在算法和数据结构的学习中。二叉查找树的主要特性是每个节点的左子树只包含小于该节点的元素,右子...

    c++实现二叉查找树

    ### C++ 实现二叉查找树 #### 一、引言 本文将详细介绍如何使用C++来实现一个二叉查找树(Binary Search Tree, BST),包括其基本操作:插入、删除、遍历等,并通过示例代码进行解释。二叉查找树是一种非常重要的数据...

    VC++实现二叉查找树

    二叉查找树(Binary Search Tree,简称BST),是一种特殊的二叉树数据结构,它具有以下特性:对于树中的任意一个节点,其左子树中所有节点的值都小于该节点的值,右子树中所有节点的值都大于该节点的值。这种性质...

    C++模板类二叉查找树的实现

    在C++编程中,二叉查找树(Binary Search Tree,简称BST)是一种常见的数据结构,它具有以下特性:对于任意节点,其左子树中的所有节点的值都小于该节点的值,右子树中所有节点的值都大于该节点的值。这种性质使得...

    二叉查找树c 源码

    二叉查找树(Binary Search Tree,BST)是一种特殊类型的二叉树,它的每个节点都包含一个键(key)、一个关联的值、一个指向左子树的引用和一个指向右子树的引用。在二叉查找树中,对于任意节点,其左子树中的所有...

    二叉查找树的C语言实现——插入,删除,查找

    二叉查找树(Binary Search Tree,BST)是一种特殊的二叉树数据结构,它具有以下特性:对于树中的每个节点,其左子树上的所有节点的值都小于该节点的值,而右子树上的所有节点的值都大于该节点的值。这样的特性使得...

    第六课_二分查找与二叉查找树.pdf

    二分查找有递归和循环两种实现方式。递归实现是通过函数自身调用自身来完成查找过程;而循环实现则是使用循环结构来重复查找步骤。两种方式各有优劣,但都可以达到相同的查找效果。 二分查找的变种之一是旋转数组...

    python实现二叉查找树1

    【二叉查找树(Binary Search Tree)】是计算机科学中的一种特殊的树结构,它具有以下特性: 1. **定义**: - 二叉查找树(BST)是一种自平衡的二叉树,其中每个节点包含一个键(key)、关联的值、左子节点和右子...

    最优二叉查找树

    - **二叉查找树**(Binary Search Tree,简称BST)是一种数据结构,其中每个节点最多有两个子节点,并且满足以下性质:对于任意节点,其左子树中的所有节点的值小于该节点的值,其右子树中的所有节点的值大于该节点...

    二叉查找树实现源码(C、C++、JAVA)

    在C、C++和Java这三种编程语言中实现二叉查找树,主要涉及以下几个关键操作: **插入操作:** - 首先,从根节点开始,比较新节点的键值与当前节点的键值。 - 如果新节点的键值小于当前节点,移动到当前节点的左子树...

    二叉查找树完整C++代码

    二叉查找树(Binary Search Tree,BST)是一种特殊的二叉树结构,它的每个节点都包含一个键值(key)、一个指向左子树的指针和一个指向右子树的指针。在二叉查找树中,对于任意节点,其左子树中的所有节点的键值都...

    二叉查找树

    二叉查找树(Binary Search Tree,BST)是一种特殊的二叉树数据结构,它具有以下特性:对于树中的每个节点,其左子树上的所有节点的值都小于该节点的值,而右子树上的所有节点的值都大于该节点的值。这个特性使得在...

    二叉查找树python二叉查找树源码

    二叉查找树(Binary Search Tree,BST),也称为二叉排序树,是一种特殊的二叉树数据结构。它的每个节点都包含一个键(key)、一个关联的值、一个指向左子节点的指针和一个指向右子节点的指针。在二叉查找树中,对于...

    二叉查找树的C++实现

    二叉查找树(Binary Search Tree),也称作有序或排序二叉树,是一种特殊的二叉树数据结构,其每个节点包含一个键(key)和两个指针(指向左子树和右子树)。对于任何节点来说,其左子树中的所有节点的键均小于它的键...

    Objective C二叉查找树

    在Objective-C中实现二叉查找树,我们需要定义一个表示节点的数据结构,并提供相应的操作方法。以下是一些可能的关键知识点: 1. **节点结构**: - 定义一个`Node`结构体或类,包含键、值、左子节点和右子节点的...

    一种高效二叉查找树---红黑树

    在计算机科学领域,二叉查找树(Binary Search Tree, BST)是一种非常重要的数据结构,它能够有效地实现查找、插入和删除等基本操作。然而,在某些情况下,普通的二叉查找树可能会退化成链式结构,导致性能下降。为了...

    实现二叉排序树的各种算法

    二叉排序树(Binary Sort Tree,BST),也称为二叉查找树或二叉搜索树,是一种自平衡的二叉树数据结构,它在处理搜索、插入和删除操作时具有较高的效率。二叉排序树的主要特性是:对于任意节点,其左子树中的所有...

    C语言实现二叉查找树(二插排序树)的基本操作。.zip

    二叉查找树,又称二叉排序树,是一种在计算机科学中广泛应用的数据结构。它具有以下特性:对于任意一个节点,其左子树中的所有节点的值都小于该节点的值,而右子树中所有节点的值都大于该节点的值。这样的结构使得...

    二叉查找树 C++源代码 数据结构

    二叉查找树(Binary Search Tree,BST)是一种特殊类型的二叉树,...在学习数据结构基础,如张力译版的书籍中,二叉查找树是重要的知识点之一,理解并掌握其原理和实现方法对于提升编程技能和解决问题的能力大有裨益。

Global site tag (gtag.js) - Google Analytics