search


※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

  • lower_bound
    key以上の値が出現する最初のインデックスを返す
    int lower_bound(int[] a, int key) {
    	int lb = 0, ub = a.length-1;
    	if (a[lb] == key) return lb; 
    	while (ub - lb > 1) {
    		int mid = (ub + lb) / 2;
    		if (a[mid] >= key)
    			ub = mid;
    		else
    			lb = mid;
    	}
    	return ub;
    }
  • upper_bound
    keyより大きい値が出現する最初のインデックスを返す
    int upper_bound(int[] a, int key) {
    	int lb = 0, ub = a.length-1;
    	if (a[ub] == key) return ub + 1;
    	while (ub - lb > 1) {
    		int mid = (ub + lb) / 2;
    		if (a[mid] > key)
    			ub = mid;
    		else
    			lb = mid;
    	}
    	return lb+1;
    }