[알고리즘] 이분탐색

이분탐색은 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다. 리스트의 모든 값을 비교하는 완전 탐색의 경우에는 O(n)의 시간 복잡도를 가지는 반면에 이분탐색은 O(logn)의 시간 복잡도를 가져 빠른 탐색이 가능하다.

 

이분탑색을 사용하기 위해서 필요조건이 있다.

1. 리스트의 데이터가 정렬되어야 한다.

-> 정렬이 되어있지 않으면 원하는 데이터가 어느 범위에 있는 특정 짓을 수가 없기 때문이다.

2. 무작위 접근이 가능해야한다.(Random Access)

-> 원하는 인덱스의 값을 얻기위해서 O(1) 접근이 불가능한 연결 리스트의 경우에는 이분탐색의 의의가 퇴색되기 때문이다.

 

기본적인 이분탐색의 알고리즘은 아래의 그림과 같다.

 

값이 포함된 범위 [left, right]에서 그 중간 값이니 mid의 값을 검사하여 원하는 target이 포함된 범위를 1/2로 줄이면서 해당 값의 인덱스를 찾는 알고리즘이다.

자바 코드로 해당 알고리즘을 구현하면 다음과 같다.

public int binarySearch(int[] arr, int target) {
    int start = 0;
    int end = arr.length - 1;
    int mid = 0;

    while (start <= end) {
        mid = (start + end) / 2;
        if (target == arr[mid]) {
            return mid;
        }else if (arr[mid] < target) {
            start = mid + 1;
        }else if (target < arr[mid]) {
            end = mid - 1;
        }
    }
    throw new NoSuchElementException("can't find target.");
}

이 코드는 배열에 원하는 target값이 있다면 해당 값의 인덱스를 리턴한다. 하지만 배열에 해당 값이 존재하지 않는다면 예외를 발생시킨다.

 

만약 내가 원하는 인덱스가 target에 가장 근접한 값을 알고 싶다면 다음 코드를 그대로 활용할 수 있을까? target이 존재한다면 target과 같은 값을 가진 인덱스가 가장 근접한 값이기 때문에 사용이 가능하지만 배열에 target과 동일한 값이 존재하지 않는다면 해당 코드를 그대로 사용하기에는 무리가 있다.

만약 target이 배열에 2개 이상 포함된 경우는 어떠한가? 여러개의 target 인덱스 중에서 내가 원하는 인덱스가 그때 요구에 따라서 다르다면 이 또한 코드를 그대로 사용하기에는 힘들다.

 

이분탐색 알고리즘의 원리를 기반으로 이를 활용할 수 있어야한다.

 

위의 코드에서 조금만 변형해보자

public int binarySearch(int[] arr, int target) {
    int start = 0;
    int end = arr.length - 1;
    int mid = 0;

    while (start <= end) {
        mid = (start + end) / 2;
        if (arr[mid] <= target) {
            start = mid + 1;
        }else if (target < arr[mid]) {
            end = mid - 1;
        }
    }
    return end;
}

 

 

이 코드는 예외를 발생시키지 않는다.

이 코드를 두가지 경우에 적용해보자

1. 배열에 원하는 값이 하나 존재할 때

2. 배열에 원하는 값이 존재하지 않을 때

 

1번의 경우에는 mid가 해당 인덱스 값을 찾으면 start는 원하는 인덱스의 다음 인덱스를 저장한다.

그렇다면 탐색하는 범위에는 해당 값이 존재하지 않기 때문에 else if문이 계속해서 실행된다. end는 계속해서 줄어들면서 결국은 start-1의 인덱스 값을 저장한다. 이때 while문의 조건에 false에 해당하는 경우가 되므로 반복문을 종료한다.

start가 탐색하는 인덱스 +1 값을 저장하고 있으며 end는 start이전의 인덱스 값을 저장하고 있기 때문에 end는 원하는 값을 저장한 인덱스를 값을 지니고 있다.

 

2번의 경우에는 if조건문을 살펴보자 start는 mid가 목표 값보다 작거나 같으면 이동한다. 이때 값은 목표 값보다 클수도 작을수도 있다.(같은 경우는 2번 경우의 전제에 의해서 없다.) 하지만 해당 값이 존재하지 않아 계속해서 이 과정이 반복된다면 mid가 목표 값보다 작지만 작은 값들 중에서 가장 그 차이가 작은 경우까지 이동한다. 이때 mid+1의 값은 목표값보다 크다. start가 목표값보다 크다면 해당 if문은 while문이 반복되는 시간 동안 동작하지 않는다.

else if문에서도 if문에서 추론한 내용과 동일하게 동작한다. 결국 end에 저장된 값은 목표값과 차이가 가장 작은 큰 수에 이르면 end의 인덱스는 목표 값보다 작은 값을 저장한 인덱스를 가지게 된다.

이 두가지 경우는 while문의 조건식을 false로 만든다. end.value < mid.value < start.value 성립하기 때문이다. 

end는 배열에서 목표값보다 작지만 작은 값들 중에서 가장 근사한 값을 가진 인덱스를 지니고 있고 start는 목표값보다 크지만 큰 값들 중에서 가장 근사한 값을 가진 인덱스를 지니고 있다. 해당 값이 배열에 존재하지 않기 때문에 배열의 범위를 초과할 수도 있다.

 

위의 두가지 경우에는 적당히 활용하면 사용이 가능하다. 하지만 동일한 목표값이 여러가지 있는 경우라면 사용이 곤란하다. 배열의 길이나 탐색의 범위에 따라서 출력되는 값이 달라지기 때문에 해당 데이터가 가지는 의미를 살지 못할 수 있기 때문이다.

 

upper/lower bound

동일한 값을 여러개 가진 배열에서 원하는 값의 존재하는 처음 인덱스 값과 마지막 인덱스 값을 알 수 있다면 추가된 경우도 문제 없다. 알고리즘 문제를 해결할 때 구글링을 통해서 다른 사람들의 알고리즘을 사용하여 코드를 작성했는데 문제가 틀렸다는 경우를 경험했다. 일반적인 경우에는 문제가 없지만 특별한 경우 문제를 일으키는 코드를이 존재한다.

다음은 내가 참조한 코드이다.

 

static int lowerbound(int[] list, long target) {
    int start = 0, end = list.length -1;
	while(start < end) {
		int mid = (start+end)/2;
		if(list[mid] >= target) {
			end = mid;
		}
		else {
			start = mid+1;
		}
	}
	return start;
}

static int upperbound(int[] list, long target) {
    int start = 0, end = list.length -1;
	while(start < end) {
		int mid = (start+end)/2;
		if(list[mid] <= target) {
			start = mid+1;
		}
		else {
			end = mid;
		}
	}
	return start;
}

위의 그림처럼 lower_bound는 해당하는 목표값의 첫번째 인덱스를 출력하고 upper_bound는 해당하는 목표 값의 마지막 인덱스 + 1 를 출력한다.

 

위의 코드의 문제점은 upper_bound를 탐색하는 경우이다. 1, 2, 5, 5, 5 로 이루어진 배열이 있다고 가정하자 이때 탐색할 값은 5이다. 위의 코드를 활요한다면 upper_bound는 4를 반환한다. 위의 그림과 차이가 보이지 않는가? 목표 값의 마지막 인덱스 + 1이 아니라 목표 값의 마지막 인덱스를 출력하였다.  1, 2, 5, 5, 4 의 배열에서 5를 탐색하는 경우에도 4를 반환한다. 함수를 설계한 기본 개념에서 벗어난 출력값을 반환하는 위의 코드는 오류 가능성을 내포하고 있는 코드이기 때문에 지양해야한다고 생각한다.

 

public static int upperBound(int[] list, int target) {
	int left = 0;
    int right = list.length-1;
    int mid;
    while (right >= left) {
        mid = (left + right) / 2;
        if (list[mid] > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return left;
}
public static int lowerBound(int[] list, int target) {
	int left = 0;
    int right = list.length-1;
    int mid;
    while (right >= left) {
        mid = (left + right) / 2;
        if (list[mid] >= target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

다음과 같이 수정한 코드는 위의 함수 설계 개념을 여전히 고수하고 있다. 모든 케이스 생각한 것은 아니지만 해당 문제의 테스트 케이스를 모두 통과한 코드이기도 하고 위에서 발견한 오류가 발생하지 않는다. 아직까지는 해당 코드의 문제를 발견하지 못했지만 혹시 다른 문제가 있다면 댓글을 달아주면 감사할 듯하다. 

 

 

출처

https://wootool.tistory.com/62

https://ko.wikipedia.org/wiki/%EC%9D%B4%EC%A7%84_%EA%B2%80%EC%83%89_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98