二分查找

原创
2018/06/24 00:33
阅读数 134

        二分查找,也称折半查找、二分搜索,是一种在有序数组中查找某一特定元素的搜索算法。搜素过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜素过程结束;如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。如果在某一步骤数组已经为空,则表示找不到指定的元素。这种搜索算法每一次比较都使搜索范围缩小一半,其时间复杂度是O(logN)。

package com.query.half.utils;

import java.util.Comparator;

/**
 * 二分查找  工具类
 * @author huang
 *
 */
public class HalfQueryUtil {

	private HalfQueryUtil() {
		super();
	}

	public static <T> int binarySearch(T[] list, T key, Comparator<T> comparator) {
		if(null == list || null == comparator) {
			return -1;
		}
		int retIndex = -1;
		int start = 0;
		int end = list.length;
		int middle = 0;
		int compareResult = 0;
		while(start < (end-1)) {
			middle = (start + end) >>> 1;
			compareResult = comparator.compare(list[middle], key);
			if(compareResult > 0) {
//				start = start;
				end = middle;
			} else if(compareResult < 0) {
				start = middle;
//				end = end;
			} else {
				retIndex = middle;
				break;
			}
		}
		return retIndex;
	}
	
	public static <T extends Comparable<T>> int binarySearch(T[] list, T key, int start, int end) {
		if(start <= end) {
			int middle = (start + end) >>> 1;
			int compareResult = key.compareTo(list[middle]);
			if(compareResult > 0) {
				start = middle + 1;
//				end = end;
				return binarySearch(list, key, start, end-1);
			} else if(compareResult < 0) {
//				start = start;
				end = middle - 1;
				return binarySearch(list, key, start, end-1);
			} else {
				return middle;
			}
		}
		return -1;
	}	
}

注:需要注意的是计算中间位置时不应该使用(high+ low) / 2的方式,因为加法运算可能导致整数越界,这里应该使用以下三种方式之一:

end + (start – end) / 2

end + (start – end) >> 1

(end + start) >>> 1

 

展开阅读全文
加载中
点击引领话题📣 发布并加入讨论🔥
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部