`
rest001555
  • 浏览: 11704 次
  • 性别: Icon_minigender_1
  • 来自: 西安
社区版块
存档分类
最新评论

二分查找的两种实现方法

阅读更多
二分查找又名折半查找法,实现思路可以到网上找到,在此就不在说了。二分查找有两种实现方法,一种方法是:使用循环遍历,结束条件是:low > high;另一种方法是:使用递归,结束条件也是:low > high。代码如下:

public class BinarySearchTest {

	public static void main(String[] args) {
		int arr[] = new int[10];
		int data = -1;
		for (int i = 1; i <= 10;i++) {
			arr[i - 1] = i; 
		}
		SortUtil.showArr(arr);
		System.out.println(binarySearch(arr,data));
		System.out.println(binarySearch(arr,0,arr.length - 1,data));
	}
	
	/**
	 * 循环实现
	 * @param arr
	 * @param data
	 * @return
	 */
	public static int binarySearch(int[] arr ,int data){
		int low = 0,high = arr.length - 1,index = -1;
		while (low <= high) {
			int mid = (low + high)/2;
			if (arr[mid] == data) {
				index = mid;
				break;
			} else if (arr[mid] > data) {
				high = mid - 1;
			} else if (arr[mid] < data) {
				low = mid + 1;
			}
		}
		return index;
	}
	
	/**
	 * 递归实现
	 * @param arr
	 * @param data
	 * @return
	 */
	public static int binarySearch(int[] arr,int low,int high,int data) {
		int mid = (low + high)/2;
		if (arr[mid] == data) {
			return mid;
		} else if (low <= high && arr[mid] > data) {
			return binarySearch(arr,low,mid - 1,data);
		} else if (low <= high && arr[mid] < data) {
			return binarySearch(arr,mid + 1,high,data);
		} else {
			return -1;
		}
	}
}


使用到的工具类:SortUtil 代码如下:

public final class SortUtil {
	private SortUtil(){};
	
	public static void showArr(int[] arr) {
		for (int i : arr) {
			System.out.print(i);
			System.out.print('\t');
		}
		System.out.println();
	}
}



文章来自:http://bo-hai.iteye.com/blog/1997019
用于温习.
分享到:
评论

相关推荐

    数据结构实验——查找(二分查找&顺序查找)

    一、实验目的: 熟悉各种查找算法及其复杂性,能够根据实际情况选择合适的存储结构。 二、实验要求: 1、掌握查找的基本方法。 2、提交实验报告,报告...编程分别对有序顺序表的顺序查找,二分查找算法进行实现。

    快速排序对数组排序,二分查找。

    C实现的两种二分查找。 先用快速排序对数组排序,再二分查找。

    二分查找办法

    两种二查找的方法,健忘版以及识别版本,但是按效率来说健忘版比识别办好

    二分查找算法

    Description 编写Search_Bin函数,实现在一个...输出分两种情形: 1.如果key值存在,则输出其在表中的位置x(表位置从0开始),格式为The element position is x. 2.如果key值不存在输出:"The element is not exist.

    PHP二分查找算法的实现方法示例

    主要介绍了PHP二分查找算法的实现方法,简单分析了二分查找算法的原理,并结合具体实例形式给出了php基于循环与递归两种方法实现二分查找的相关操作技巧,需要的朋友可以参考下

    Java实现的两种常见简单查找算法示例【快速查找与二分查找】

    主要介绍了Java实现的两种常见简单查找算法,结合具体实例形式分析了java快速查找与二分查找的原理与简单实现技巧,需要的朋友可以参考下

    二分搜索的MATLAB代码

    %BINARYSEARCH 二分搜索法查找,其中L是有序数列。代码包含递归法和迭代法两种实现方法

    C++实现折半查找(二分查找)算法(含实现原理和步骤)

    折半查找,也称为二分查找(Binary Search)或对数查找(Logarithmic Search),是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束;...

    数据结构 二分查找 上机实验

    输出分两种情形: 1.如果key值存在,则输出其在表中的位置x(表位置从0开始),格式为The element position is x. 2.如果key值不存在输出:"The element is not exist." Sample Input 6 1 3 5 7 9 10 5 Sample ...

    使用PHP实现二分查找算法代码分享

    第一种方法: 【二分查找要求】:1.必须采用顺序存储结构 2.必须按关键字大小有序排列。 【优缺点】折半查找法的优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除困难。因此,折半...

    Python实现二维有序数组查找的方法

    对于每一行进行二分查找,然后查找过程可以把某些列排除掉,这是大家都能想到的基本的思路。 比较好的另一种思路是,首先选取数组右上角的数字,如果该数字等于要查找的数字,则查找结束;如果该数字大于要查找的...

    查找算法.doc

    简单顺序查找、有序表的二分查找、索引表的顺序查找。这里主要介绍前两种。 一、简单顺序查找 简单顺序查找对数据表的特性没有要求,即是否具有递增递减特性基本不影响查找的性能。基本就是从表的一段开始逐个比较...

    JAVA冒泡排序和二分查找的实现

    本文详细介绍了JAVA冒泡排序和二分查找的实现,虽然这两种算法比较简单,但是确实我们必须需要掌握的。下面来看看。

    二分三分哈希

    二分:在一个单调有序的集合中查找元素,每次将集合分为左右两部分,判断解在哪个部分中并调集集合上下界,重复直到找到目标元素。时间复杂度:O(logn) 三分:最基础的作用,寻找凸性函数极值 哈希:Hash,一般翻译...

    C经典算法之二分查找法

    主要介绍了C经典算法之二分查找法的相关资料,这里提供两种方法帮助大家实现这样的功能,需要的朋友可以参考下

    计算机二级公共基础知识

    在下列两种情况下也只能采用顺序查找: ①如果线性表为无序表,则不管是顺序存储结构还是链式存储结构,只能用顺序查找; ②即使是有序线性表,如果采用链式存储结构,也只能用顺序查找。 1.7.2 二分法查找 二分法...

    查找代码C++来自《C++数据结构与程序设计》Robert L.Kruse Alexander J.Ryba

    用迭代和非迭代两种方法实现二分查找,同时还用了C++的模板和继承等方法。

    数据结构 查找算法 源代码

    数据结构 查找 源代码 二分查找的算法源码,两种算法的效率比较

    python实现二分搜索.md

    二分搜索 二分搜索(Binary Search)是一种用于在有序数组中查找元素的高效算法。它通过将数组分成两半并比较目标元素与中间元素的值来快速确定目标元素的位置。

Global site tag (gtag.js) - Google Analytics