소트되어 있는 상태의 배열이라면...
배열의 중간부터 검색해나가면 O(logN)으로 검색할수있습니다...
intArr[100]의 경우 배열의 중간인 intArr[50]의 값을 Val과 비교해서 크면 intArr[25]의 수와 작으면 intArr[75]의 수와 비교합니다...이런식으로 계속 중간의 수만 비교하면 될것같은데여..
아래 간단하게 같은수의 첨자찾는 방법을 적어봤는데여...실행은 안해봤는데 이런식으로 하면 될것같네여..
결과야 장담못하지만여...^^
/***********************************/
#define ARRCNT   100
.
.
.
.
int IntArr[ARRCNT];
for(int i=0; i<ARRCNT; i++) IntArr[i] = 2*i;
int Val = 55;
int cnt,Index;
Index=cnt=ARRCNT/2;
while(1)
{
cnt/=2;
if(Val>IntArr[Index]) Index-=cnt;
else if(Val<IntArr[Index]) Index+=cnt;
else break;
}
/***********************************/



Jisang Yoo 님이 쓰신 글 :
: int IntArr[100];
: for(int i=0 ; i<100 ; i++)
:   IntArr[i] = 2*i;
: int Val = 55;
:
: 위에서처럼 int의 배열인 IntArr가 있고, 배열 IntVarr 은 크기가 작은 수부터 큰 수의 순서로 소트되어있는 상태라고 합시다.
: 그리고 또다른 int 변수인 Val 이 있는데, 하고 싶은 것은,
: IntArr 배열 안에 있는 수들 중에서 Val 보다 작은 수들 중 가장 큰 수의 인덱스를 찾는 것입니다.
: 즉, IntArr 안에 있는 수들 중에서 Val보다 작은 것들 중 Val 과 가장 가까운 수를 찾는 것인데,
: 이런 일을 하는 STL 함수가 있나요?
: 이런 일을 할 때, IntArr[0] ,IntArr[1], .... 이런 식으로 순서대로 차례차례로 비교하면 O( N) 의 시간이 걸리는데,
: IntArr가 이미 소트된 상태라는 것을 이용해서 O(logN) 의 시간이 걸리는 방법으로 이 일을 해주는 STL함수가 무엇인가요?