二分法查找

import java.util.Arrays;

/**
 * 
* @项目名称：Test   
* @类名称：BinarySearch   
* @类描述：   二分法查找
* @创建人：Ansj   
* @创建时间：2011-9-13 下午02:53:47  
* @修改备注：   
* @version    
*
 */
public class BinarySearch {
	public static void main(String[] args) {
		int[] ints = {12,123,21,123,1,432,23,42,3,123,124,3,5435,66,456554,435,423,42,1} ;
		
		int find = 66 ;
		
		//先对数组排序
		Arrays.sort(ints) ;
		
		for (int i = 0; i < ints.length; i++) {
			new BinarySearch().search(ints, ints[i]) ;
		}
		
		
	}
	
	public void search(int[] ints , int find){
		search(ints,0,ints.length,find) ;
	}
	
	
	public void search(int[] ints , int start , int end , int find){
		if(ints[(start+end)/2]==find){
			System.out.println((start+end)/2);
		}else if(ints[(start+end)/2] > find){
			search(ints , start , (start+end)/2 , find) ;
		}else{
			search(ints , (start+end)/2 , end , find) ;
		}
	}
	
}

评论

4 楼 ansjsun 2011-09-25  

yinpeng21cn 写道

Arrays.sort(ints)用来做什么？排序；排序用来做什么？介绍二分法查找算法；
其实想想，真正sort的时候都能对数组排序了，为什么不能当时就找出需要的那个数字呢？
所以我觉得不要用sort方法排序了，自己写一个吧，时间复杂度会更小。

二分查找法的是建立在一次排序多次查找的基准上的..
如果就是为了在无序状态下一次查找..用二分就脑残了..

排序有排序的算法...不是这个的需求啊

3 楼 yinpeng21cn 2011-09-24  

Arrays.sort(ints)用来做什么？排序；排序用来做什么？介绍二分法查找算法；
其实想想，真正sort的时候都能对数组排序了，为什么不能当时就找出需要的那个数字呢？
所以我觉得不要用sort方法排序了，自己写一个吧，时间复杂度会更小。

2 楼 ansjsun 2011-09-15  

liubing539 写道

还 你的二分法当赋值给find的参数 在数组ints里没有的话，就会报异常，我把你的程序改了下 就能用了 谢谢！
public static void main(String[] args) {
int[] ints = { 12, 12, 11, 9, 10, 5, 7, 1, 1 };
int start = 0;
int end = ints.length;

int find = 5;

// 先对数组排序
Arrays.sort(ints);

new Test().search(ints, start, end, find);
}

public int search(int[] ints, int start, int end, int find) {
int flag = 0;
if (ints[(start + end) / 2] == find) {
System.out.println(ints[(start + end) / 2]);
flag = 1;
return flag;
} else if ((end - start) <= 1) {
if (ints[start] == find) {
System.out.println(ints[start]);
flag = 1;
return flag;
} else if (ints[end] == find) {
System.out.println(ints[end]);
flag = 1;
return flag;
} else {
flag = 0;
return flag;
}
} else if (ints[(start + end) / 2] > find) {
if (start < (start + end) / 2) {
end = (start + end) / 2;
search(ints, start, end, find);
} else {
flag = -1;
return flag;
}

} else {
if ((start + end) / 2 < end) {
start = (start + end) / 2;
search(ints, start, end, find);
} else {
flag = -1;
return flag;
}

}

return flag;
}

其实很早以前写过..这次想用递归写还是没写好..一次写完也没仔细测呵呵..谢谢你提的意见...

这是标准的二分代码..和jdk写的一样

public static void main(String[] args) {
		int[] array = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 14, 15, 22, 232 };
		for (int i = 0; i < array.length; i++) {
			System.out.println(erFen(array,array[i])) ;
		}
	}

	public static boolean erFen(int[] array, int num) {
		int begin = 0;
		int end = array.length - 1;

		while (begin <= end) {
			int mid = (begin + end) / 2;
			if (array[mid] > num) {
				end = mid -1 ;
			} else if (array[mid] < num) {
				begin = mid +1 ;
			} else {
				return true;
			}
		}

		return false;
	}

1 楼 liubing539 2011-09-15  

还 你的二分法当赋值给find的参数 在数组ints里没有的话，就会报异常，我把你的程序改了下 就能用了 谢谢！
public static void main(String[] args) {
int[] ints = { 12, 12, 11, 9, 10, 5, 7, 1, 1 };
int start = 0;
int end = ints.length;

int find = 5;

// 先对数组排序
Arrays.sort(ints);

new Test().search(ints, start, end, find);
}

public int search(int[] ints, int start, int end, int find) {
int flag = 0;
if (ints[(start + end) / 2] == find) {
System.out.println(ints[(start + end) / 2]);
flag = 1;
return flag;
} else if ((end - start) <= 1) {
if (ints[start] == find) {
System.out.println(ints[start]);
flag = 1;
return flag;
} else if (ints[end] == find) {
System.out.println(ints[end]);
flag = 1;
return flag;
} else {
flag = 0;
return flag;
}
} else if (ints[(start + end) / 2] > find) {
if (start < (start + end) / 2) {
end = (start + end) / 2;
search(ints, start, end, find);
} else {
flag = -1;
return flag;
}

} else {
if ((start + end) / 2 < end) {
start = (start + end) / 2;
search(ints, start, end, find);
} else {
flag = -1;
return flag;
}

}

return flag;
}