Binary , lower , upper searching

이분탐색을 직접 구현하는데 자꾸 헷갈리는 부분이 많아서 정리를 해야겠다.

 

이분탐색은 원하는 값을 찾는 형태로 범위에 신경쓰지 않고 바로 구현하면 된다.

int s = 0;
int e = MAX;
int m;
while(s<=e){
	m = (s+e)/2;
    if(array[m] == wantValue) return;
    if(array[m] > wantValue) e = m-1;
    else if(array[m] < wantValue) s = m+1;
}

 

 

lower bound는 찾고자하는 값 이상의 첫번째 인덱스를 찾는 개념 

1 2 3 4 5 5 6 7 8 에서 5에 대한 lower bound의 인덱스는 4가 된다.

 

upper bound는 찾고자하는 값을 초과하는 첫번째 값의 인덱스를 찾는 개념

1 2 3 4 5 5 6 7 8 에서 5에 대한 upper bound의 인덱스는 6이 된다.

 

 

lower bound는 start<=end 단위가 아니라 start<end 단위로 사용해야 한다.

또한 중간값이 찾고자하는 값보다 크거나 같은 경우

특히 같은 경우에는 그 위치가 lower bound index가 될 수 있으므로 end = mid - 1 이 아닌 end = mid 를 적용

 

upper bound는 마찬가지로 start<end 단위를 사용하며

이상이 아닌 초과된 인덱스를 찾으므로

중간값이 찾고자하는 값보다 작거나 같은 경우는 무조건 start = mid + 1을 하여 인덱스를 계산하게 된다.

 

//lower_bound

int s = 0;
int e = MAX;
int m;

while(s<e){
	m = (s+e)/2;
    if(array[m] >= wantValue) e = m;
    else s = m+1;
}

return e;

// upper_bound

while(s<e){
	m = (s+e)/2;
    if(array[m] > wantValue) e = m;
    else s = m+1;
}

return e;