2分探索(binary search)

リポジトリ
 binary_search - C++ Reference
lower_bound - C++ Reference
upper_bound - C++ Reference
※ほぼ全部未検証

ソート済のデータに対して $O(\log n)$ で探索を行う( $n$ はデータ数)。
たいていの言語に標準で2分探索の関数が用意されてるので、実装する意味はあまりない。
JavaならCollections.binarySearch()やArrays.binarySearch()、C++ならbinary_search()を使えばおｋ。

public static <T> int _binarySearch(T[] a, int fromIndex, int toIndex, T key, Comparator<? super T> c){
	int lb = fromIndex, ub = toIndex-1;
	while( lb <= ub ){
		int mid = (lb + ub) / 2, cmp = c.compare(a[mid], key);
		if( cmp == 0 ) return mid;		// exit success
		if( cmp < 0 )	lb = mid + 1;
		else 		ub = mid-1; 	        // x[mid] > key
	}
	return -1; 					//exit failure
}
public static <T> int _binarySearch(T[] a, T key, Comparator<? super T> c){
	return _binarySearch(a, 0, a.length, key, c);
}
public static <T extends Comparable <? super T>> int _binarySearch(T[] a, int fromIndex, int toIndex, T key){
	return _binarySearch(a, fromIndex, toIndex, key, new Comparator<T>(){
		@Override public int compare(T o1, T o2) { return o1.compareTo(o2); }
	});
}
public static <T extends Comparable<? super T>> int _binarySearch(T[] a, T key){
	return _binarySearch(a, 0, a.length, key, new Comparator<T>(){
		@Override public int compare(T o1, T o2) { return o1.compareTo(o2); }
	});
}

上限(upper bound)

2分探索を応用して、ソート済みのデータに対して、キーの存在範囲を $O(\log n)$ で求められる。
上限を求めるのにC++ならupper_bound()があるが、javaにはなかったので(知らないだけかもしれない)作ってみた。
※キーの存在範囲は[下限, 上限)とする。

public static <T> int upperBound(T[] a, int fromIndex, int toIndex, T key, Comparator<? super T> c){
	int lb = fromIndex - 1, ub = toIndex;
	while(ub - lb > 1){			//range of solution > 1
		int mid =(lb + ub) / 2, cmp = c.compare(a[mid], key);
		if( cmp <= 0 )	lb = mid;	//[mid,ub)
		else		ub = mid;	//[lb,mid)
	}
	return ub; 				//ub = lb + 1, [lb, ub)
}
public static <T> int upperBound(T[] a, T key, Comparator<? super T> c){
	return upperBound(a, 0, a.length, key, c);
}
public static <T extends Comparable <? super T>> int upperBound(T[] a, int fromIndex, int toIndex, T key){
	return upperBound(a, fromIndex, toIndex, key, new Comparator<T>(){
		@Override public int compare(T o1, T o2) { return o1.compareTo(o2); }
	});
}
public static <T extends Comparable<? super T>> int upperBound(T[] a, T key){
	return upperBound(a, 0, a.length, key, new Comparator<T>(){
		@Override public int compare(T o1, T o2) { return o1.compareTo(o2); }
	});
}

下限(lower bound)

同様に、ソート済みのデータに対してキーの存在範囲の下限を $O(\log n)$ で求められる。
下限を求めるのにC++ならlower_bound()がある。
※キーの存在範囲は[下限, 上限)とする。

public static <T> int lowerBound(T[] a, int fromIndex, int toIndex, T key, Comparator<? super T> c){
	int lb = fromIndex - 1, ub = toIndex;
	while(ub - lb > 1){ 			//rage of solution > 1
		int mid = (lb + ub) / 2, cmp = c.compare(a[mid], key);
		if( cmp >= 0 )	ub = mid;	//(lb,mid]
		else		lb = mid;	//(mid,ub]
	}
	return ub; 				//(lb, ub], ub = lb + 1 → [ub, ub+1)
}
public static <T> int lowerBound(T[] a, T key, Comparator<? super T> c){
	return lowerBound(a, 0, a.length, key, c);
}
public static <T extends Comparable <? super T>> int lowerBound(T[] a, int fromIndex, int toIndex, T key){
	return lowerBound(a, fromIndex, toIndex, key, new Comparator<T>(){
		@Override public int compare(T o1, T o2) { return o1.compareTo(o2); }
	});
}
public static <T extends Comparable<? super T>> int lowerBound(T[] a, T key){
	return lowerBound(a, 0, a.length, key, new Comparator<T>(){
		@Override public int compare(T o1, T o2) { return o1.compareTo(o2); }
	});
}

キーの数

upper boundとlower boundを使うと、ソート済みのデータにキーが何個含まれているかを $O(\log n)$ で求めることができる。

public static <T> int keyCount(T[] a, int fromIndex, int toIndex, T key, Comparator<? super T> c){
	return upperBound(a, fromIndex, toIndex, key, c) - lowerBound(a, fromIndex, toIndex, key, c);
}
public static <T> int keyCount(T[] a, T key, Comparator<? super T> c){
	return keyCount(a, 0, a.length, key, c);
}
public static <T extends Comparable <? super T>> int keyCount(T[] a, int fromIndex, int toIndex, T key){
	return keyCount(a, fromIndex, toIndex, key, new Comparator<T>(){
		@Override public int compare(T o1, T o2) { return o1.compareTo(o2); }
	});
}
public static <T extends Comparable<? super T>> int keyCount(T[] a, T key){
	return keyCount(a, 0, a.length, key, new Comparator<T>(){
		@Override public int compare(T o1, T o2) { return o1.compareTo(o2); }
	});
}