lower_bound()

lower_bound()について

int A[14] = {1,1,2,2,2,4,5,5,6,8,8,8,10,15};
int *pos;
int idx;

pos = lower_bound(A,A+14,3);//3以上の値の先頭のものを指す
idx = distance(A,pos);//Aは0番目, posは5番目を指しているので5

ちなみに要素の最大値よりも大きい数を指定した場合

int A[14]={1,1,2,2,2,4,5,5,6,8,8,8,10,15};
int *pos;
pos = lower_bound(A,A+14,16);
cout<<*pos<<endl;//-1282435328

という値が返ってきた.
lower_bound()で探索を行う.

if(A[*lower_bound(A,A+n,key)]==key)
	return distance(A,lower_bound(A,A+n,key))
else 
	return NOT_FOUND

配列上の初めてkeyを超える値がkeyならばその位置を返し,それがkeyでなければNOT_FOUNDを返す.

#include <bits/stdc++.h>
using namespace std;
#define NOT_FOUND -1
int search(int A[],int n,int key)
{
	int *pos = lower_bound(A,A+14,key);
	if(*pos==key)
		return distance(A,pos);
	else
		return NOT_FOUND;
}

int main()
{
	int A[14]={1,1,2,2,2,4,5,5,6,8,8,8,10,15};
	cout<<search(A,14,3)<<endl;//-1
	cout<<search(A,14,10)<<endl;//12
	return 0;
}