首页 > 代码库 > 折半查找
折半查找
给定一个整数X和整数A0，A1，…，AN-1，后者已经预先排序并在内存中，求下标i使得Ai = X ， 如果X不在数据中则返回i = -1 。
明显的解法是从左往右扫描，花费线性时间。但是这个算法没有用到该表已经排序这个事实。
折半检索（binary search，二分法检索）策略：
/** * Performs the standard binary search. *@return index where item is found, or -1 if not found. */ public static <AnyType extends Comparable<? super AnyType>> int binarySearch( AnyType [] a , AnyType x ) { int low = 0 ; high = a.length - 1 ; while(low <= high ) { int mid =(low + high)/2; if(a[mid].compareTo(x)<0) low = mid +1 ; else if (a[mid].compareTo>0) high = mid -1 ; else return mid ;//Found } return NOT_FOUND ; //NOT_FOUND is defined as -1 ; }复杂度为O(logN)。
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。