search - procom @ ウィキ

• 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;
  }