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

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

发表于: 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

    震惊

    震惊

版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号