当前位置:首页 > 开发 > 编程语言 > 搜索 > 正文

二分搜索的递归和循环实现

发表于: 2013-10-23   作者:come_for_dream   来源:转载   浏览次数:
摘要: 二分搜索,指的是对已经排好序的数据进行搜索,也叫折半查找。下面我用递归和非递归实现了这一个算法 /** * 二分搜索的递归实现 * * @param a * @param x * @return */ public int BSearch(int[] a, int x) { int left = 0, right = a.length - 1;

二分搜索,指的是对已经排好序的数据进行搜索,也叫折半查找。下面我用递归和非递归实现了这一个算法

/**
	 * 二分搜索的递归实现
	 * 
	 * @param a
	 * @param x
	 * @return
	 */
	public int BSearch(int[] a, int x) {
		int left = 0, right = a.length - 1;

		return search(a, x, left, right);
	}

	public int search(int[] a, int x, int left, int right) {

		int mid = (left + right) / 2;
		
		if(left>right){
			return -1;
		}

		if (a[mid] == x) {
			return mid;
		}

		if (a[mid] > x) {
			return search(a, x, left, mid - 1);
		}

		else
			return search(a, x, mid + 1, right);

	}

	/**
	 * 二分搜索的循环实现
	 * 
	 * @param a
	 * @param x
	 * @return
	 */
	public int search(int[] a, int x) {
		int left = 0, right = a.length - 1;
		for (; left <= right;) {
			int mid = (left + right) / 2;
			if (a[mid] == x)
				return mid;
			if (a[mid] > x) {
				right = mid - 1;
			} else
				left = mid + 1;
		}
		return -1;

	}

 

二分搜索的递归和循环实现

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
1、 递归的定义 顺序执行、循环和跳转是冯·诺依曼计算机体系中程序设计语言的三大基本控制结构,这
对于拿到的相亲情况表,我们不妨将其转化成一个图。将每一个人作为一个点(编号1..N),若两个人之间
分治法的基本思想:将一个规模为n的问题,分解为k个规模较小的子问题,这些子问题互相独立且与原问
在学习iphone开发教程的中第8章(也就是《iOS5开发基础教程》最新版的“08 - Sections2”下载地址:
K Best Time Limit: 8000MS Memory Limit: 65536K Total Submissions: 5288 Accepted: 1431 Case Ti
一、if 1.单分支 if(表达式)语句;或者 if(表达式){语句1;语句2;},表达式后面非0时,执行语句 案
1 #include<iostream> 2 #include<string> 3 #include<algorithm> 4 #include<
Coding多了,递归算法是非常常见的,最近我一直在做树形结构的封装,所以更加的离不开递归算法。所
  对于栈有些问题还不是很熟悉,所以暂时需要些时间去理解,需要多写些代码去体会,,栈还有一个
#include<iostream> #include<string> using namespace std; void swap(char &a,char &
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号