16boke - 一路博客

用java实现的简单的二分查找算法

一、什么是二分查找

二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除困难。因此,折半查找方法适用于不经常变动而查找频繁的有序列表。首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功。

二、实例

查找一给定的值是否在指定的数组中,如果存在输出在数组中的下标,如果不存在则输出-1

public static int getIndex(int target, int[] array) {
		if (array == null || array.length == 0)
			return -1;
		if (target < array[0] || target > array[array.length - 1])
			return -1;
		int left = 0;
		int right = array.length - 1;
		int mid = (left + right) / 2;
		while (left <= right) {
			if (target < array[mid])
				right = mid - 1;
			if (target > array[mid])
				left = mid + 1;
			if (target == array[mid])
				return mid;
			mid = (left + right) / 2;
		}
		return -1;
	}
public static void main(String[] args) {
	int num[] = { 2, 3, 4, 6, 10, 20, 31, 35, 42, 53, 60, 90 };
	System.out.println(getIndex(7, num));
}