二分查找

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