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

二分查找

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

    震惊

    震惊

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