이분탐색의 경계설정

 

 

맨날 이분탐색 문제를 풀 때마다 while문의 탈출 조건으로 start < end 혹은 start <= end, 

또 범위를 줄여나갈 때도 left = mid, mid+1, right = mid-1, mid 등등.. 너무 생각할게 많았고 항상 어려워서 이번에 정리를 해보려 한다.

 

 

 

while(start <= end)

 

기본적으로 찾는 값이 중간 값보다 클 경우 start = mid+1, 작은 경우에는 end = mid -1을 수행한다.

 

end = mid -1 인 경우 답을 어떻게 찾아올 수 있을까?

예를 들어 [1, 3, 3, 5] 라는 배열에서 Lower Bound를 찾는 경우를 생각해보자.  

먼저 mid의 index는 1이 된다.

arr[mid]는 3이고, target도 3이므로, Lower Bound를 찾는 방법에 따라서 end를 줄이게 된다.

 

현재 상태에서 start는 0, end는 mid -1의 값인 0이 된다. while문의 조건이 start <= end이므로 조건식이 true가 되며 한번 더 루프를 수행한다.

즉 mid도 0이고, arr[mid]는 target보다 작으므로 start를 늘리게 된다.

이 상태가 되면 start는 1, end는 0이므로 조건식을 벗어나게된다.

이 경우 우리가 원하는 값은 start의 값인 1이 된다.

 

 

 

 

값의 인덱스를 단순히 찾는 경우

int start = 0;
int end = list.length-1;

while (start <= end) {
    int mid = (start + end) >>> 1;


    if (arr[mid] < target)
        start = mid + 1;
    else if (arr[mid] > target)
        end = mid - 1;
    else
        return mid; // key found
}
return -1;  // key not found

 

 

 

UPPER BOUND의 경우

int start = 0;
int end = list.length-1;

//초과하는 값
while (start <= end) {
    int mid = (start + end) >>> 1;


    if (arr[mid] > target) //중간값이 원하는 값보다 클 경우, 중간값이 작아져야 하므로 end를 줄인다
         end = mid - 1;
    else //만약 중간값과 같다면? -> 더 우측 범위를 탐색하기 위해 start를 늘린다.
        start = mid + 1;
}
return end+1;//or start

 

반환이 end +1 또는 start인 이유:

Upper Bound에서 만약 [1,2,2,4]에서 2의 Upper Bound를 찾는 경우를 생각해보자.

 

첫 루프->

start =0, end =3, mid = 1, -> arr[1] = 2 = target이므로  start = 2, end=3

 

두번째 루프 ->

start =2, end =3, mid = 2, -> arr[2] = 2 = target이므로  start = 3, end=3

 

세번째 루프 ->

start =3, end=3, mid=3 -> arr[3] = 4 > target이므로 end = 2 start = 3

 

 

 

또 Upper Bound에서 만약 [1,2,4]에서 2의 Upper Bound를 찾는 경우를 생각해보자.

 

첫 루프->

start =0, end =2, mid = 1, -> arr[1] = 2 = target이므로  start = 2, end=2

 

두번째 루프 ->

start =2, end =2, mid = 2, -> arr[2] = 4 > target이므로  start = 2, end=1

 

 

즉 같은 값을 찾았을 때 end가 마지막에 1이 줄어들기에 end를 1 늘려주거나 start를 반환해야 한다.

 

 

 

값이 없는 경우라면 ???

 

Upper Bound에서 만약 [1,2,2,4]에서 3의 Upper Bound를 찾는 경우를 생각해보자.

 

첫 루프->

start =0, end =3, mid = 1, -> arr[1] = 2 < target이므로  start = 2, end=3

 

두번째 루프 ->

start =2, end =3, mid = 2, -> arr[2] = 2 < target이므로  start = 3, end=3

 

세번째 루프 ->

start =3, end=3, mid=3 -> arr[3] = 4 > target이므로 end = 2 start = 3

 

 

 

또 Upper Bound에서 만약 [1,2,4]에서 3의 Upper Bound를 찾는 경우를 생각해보자.

 

첫 루프->

start =0, end =2, mid = 1, -> arr[1] = 2 < target이므로  start = 2, end=2

 

두번째 루프 ->

start =2, end =2, mid = 2, -> arr[2] = 4 > target이므로  start = 2, end=1

 

 

 

 

 

 

 

LOWER BOUND의 경우

int start = 0;
int end = list.length-1;

//초과하는 값
while (start <= end) {
    int mid = (start + end) >>> 1;


    if (arr[mid] < target) //중간값이 원하는 값보다 작을 경우,중간값이 커저야 하므로 start를 늘린다
         start = mid + 1;
    else //만약 중간값과 같다면? -> 더 좌측 범위를 탐색하기 위해 end를 줄인다.
    	end = mid - 1;
        
}
return end+1;//or start

 

반환이 end +1 또는 start 인 이유:

Lower Bound에서 만약 [1,2,2,4]에서 2의 Lower Bound를 찾는 경우를 생각해보자.

 

첫 루프->

start =0, end =3, mid = 1, -> arr[1] = 2 = target이므로  start = 0, end=0

 

두번째 루프 ->

start =0, end =0, mid = 0, -> arr[0] = 1 < target이므로  start = 1, end=0

 

target을 찾았을 때 end를 mid-1을 하기 때문에 end+1을 해주거나 이전 반복문에서 증가된 start를 사용해야 하는 것이다.

 

 

 

 

또 Lower Bound에서 만약 [1,2,4]에서 2의 Lower Bound를 찾는 경우를 생각해보자.

 

첫 루프->

start =0, end =2, mid = 1, -> arr[1] = 2 = target이므로  start = 0, end=0

 

두번째 루프 ->

start =0, end =0, mid = 0, -> arr[0] = 1< target이므로  start = 1, end=0

 

 

target을 찾았을 때 end를 mid-1을 하기 때문에 end+1을 해주거나 이전 반복문에서 증가된 start를 사용해야 하는 것이다.

 

 

 

값이 없는 경우라면 ???

 

Lower Bound에서 만약 [1,2,2,4]에서 3의 Lower Bound를 찾는 경우를 생각해보자.

 

첫 루프->

start =0, end =3, mid = 1, -> arr[1] = 2 < target이므로  start = 2, end=3

 

두번째 루프 ->

start =2, end =3, mid = 2, -> arr[2] = 2 < target이므로  start = 3, end=3

 

세번째 루프 ->

start =3, end =3, mid = 2, -> arr[3] = 4 > target이므로  start = 3, end=2

 

target보다 큰 값을 찾았을 때 end를 mid-1을 하기 때문에 end+1을 해주거나 증가된 start를 사용해야 하는 것이다.

 

 

 

또 Lower Bound에서 만약 [1,2,4]에서 3의 Lower Bound를 찾는 경우를 생각해보자.

 

첫 루프->

start =0, end =2, mid = 1, -> arr[1] = 2 < target이므로  start = 2, end=2

 

두번째 루프 ->

start =2, end =2, mid = 2, -> arr[2] =4 > target이므로  start = 2, end=1