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

二分查找

发表于: 2011-08-17   作者:Brucegaochina   来源:转载   浏览次数:
摘要: public class BinarySearch { package com.img.algorithm; public class BinarySearch { /** * @param args * @author Bruce */ public static void main(String[] args) { int[] origin
public class BinarySearch {
package com.img.algorithm;

public class BinarySearch {

	/**
	 * @param args
	 * @author Bruce
	 */
	public static void main(String[] args) {
		
		int[] origin = {1,2,3,4,5,6,7,8,9};
		int result = binarySearch(origin,8);
		
		System.out.println(result);
		
		String[] str = {"wer","erdd","dfre","bruce"};
		int re = binarySearch(str,"bruce");
		System.out.println(re);
	}
	
	public static int binarySearch(int[] arr, int target)//log 2 N <=32(32bit)
	{
		int low = 0;
		int heigh = arr.length - 1;
		
		while(low <= heigh)
		{
			int mid = (heigh + low) >>> 1;
			if(arr[mid] < target)
				low = mid + 1;
			else if(arr[mid] > target)
				heigh = mid - 1;
			else
				return mid;
		}
		return -1;
	}
	
	public static int binarySearch(String[] keys,String target)
	{
		int low = -1;
		int heigh = keys.length;
		
		while(heigh - low > 1)
		{
			int mid = (low + heigh) >>> 1;
			if(keys[mid].compareTo(target) < 0)
				heigh = mid;
			else
				low = mid;
		}
		
		if(low == -1 || keys[low].compareTo(target) != 0)
			return -1;
		else
			return low;
	}
}

	

很久以前这里的
int mid = (heigh + low) >>> 1;
是这样的
int mid = (heigh + low) / 2;
但是这个会在数组足够大的时候溢出,故用了无符号右移解决这个问题。
这个问题在Java的早期版本里面就是一个bug,后来修正了,这个bug的地址是
http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=5045582

二分查找

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
#include <iostream> using namespace std; /** * 二分查找之一: 可以找到连续重复出现的第
第一步 #include<iostream> using namespace std; int binarySearch(int a[], int x, int n)
二分查找法,顾名思义,是一种一分为二的查找算法,适用于已排序的数组(大数据量),快速地找到所
二分查找细则讨论 二分查找有两种实现方式:非递归和递归。我们首先给出非递归的实现,然后对其中的
查询二叉树是平衡树->红黑树的基础,红黑树是TreeMap和TreeSet实现的基础。 深度:根到任意节点
二分算法的定义不在多说了,百度一下就知道(支持国产) import sys source = [1,2,3,4,5,6,7,8,9,1
题意:在平面内给出n个点,问你这些点一共能组成几个不相等的正方形? 思路:几何 + 二分。先排序,
扩展方法之二分查找 版本:0.1 最后修改:2012-08-08 撰写:李现民 近期项目策划案调整,要求程序按
二分查找法要求被查找的线性表已经排序。 每一次查找,按中间索引把表分为左右两部分,通过对比中间
如果查找过程和程序执行能结合起来,那么这个过程会更加直观。 本文简单地实现了二分查找的可视化。
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号