论坛首页 入门技术论坛

Java基础:二分法查找

浏览 6616 次
该帖已经被评为新手帖
作者 正文
   发表时间:2007-12-10  
package find;

/*
 * 注意,进行二分法查找必须要将被查找的集合或数组先进行排序
 */
public class ErFenFa {
	public static void main(String[] args) {
		int[] iArray = { 4, 12, 23, 33, 45, 53, 65, 78, 88, 90 };
		// 要查找的值
		int seek = 33;
		// 类似于指针的东西
		int index = 0;
		// 查找起始下标
		int start = 0;
		// 查找结束下标
		int end = iArray.length - 1;
		// 计数器
		int count = 0;

		while (true) {
			count++;
			// 初始化数组中间值的下标
			// 原来为index = (start + end) / 2;当start + end的值超过了最大的正int值的时候, index 会变成负值,这个时候就会抛出异常.故改为这样    
			index = start + ((end - start) / 2);
			if (iArray[index] < seek) {
				start = index;
			} else if (iArray[index] > seek) {
				end = index;
			} else {
				break;
			}
		}
		System.out.println(" 二分法查找,需要比较的次数:" + count);
	}
}
   发表时间:2007-12-11  
sc_1028 写道
package find;
/*
 * 注意,进行二分法查找必须要将被查找的集合或数组先进行排序
 */
public class ErFenFa {
	public static void main(String[] args) {
		int[] iArray = { 4, 12, 23, 33, 45, 53, 65, 78, 88, 90 };
		// 要查找的值
		int seek = 33;
		// 类似于指针的东西
		int index = 0;
		// 查找起始下标
		int start = 0;
		// 查找结束下标
		int end = iArray.length - 1;
		// 计数器
		int count = 0;

		while (true) {
			count++;
			// 初始化数组中间值的下标
			index = (start + end) / 2;
			if (iArray[index] < seek) {
				start = index;
			} else if (iArray[index] > seek) {
				end = index;
			} else {
				break;
			}
		}
		System.out.println(" 二分法查找,需要比较的次数:" + count);
	}
}

楼主给的程序有bug,问题出在:
index = (start + end) / 2;
当start + end的值超过了最大的正int值的时候, index 会变成负值,这个时候就会抛出异常..
改为这样
index = start+ ((end - start) / 2);
0 请登录后投票
   发表时间:2007-12-11  
多谢提示,确实有您说的问题,我已更改,谢谢支持
0 请登录后投票
论坛首页 入门技术版

跳转论坛:
Global site tag (gtag.js) - Google Analytics