[Swift] 이분탐색이란?

1. 이분 탐색이란?

이분 탐색은 정렬된 배열에서 특정 값을 찾을 때 사용하는 알고리즘으로, 탐색 범위를 절반씩 줄여가며 원하는 값을 찾는 방법입니다.

 

2. 기본 구현

var start = 0
var end = Int.max

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

 

3. 결과값 갱신 주의점

최솟값을 찾을 때 (Lower Bound)

func findMinimum(_ array: [Int], _ target: Int) -> Int {
    var start = 0
    var end = array.count - 1
    var result = -1
    
    while start <= end {
        let mid = (start + end) / 2
        
        if array[mid] >= target {
            result = mid  // end를 줄일 때 갱신
            end = mid - 1
        } else {
            start = mid + 1
        }
    }
    
    return result
}

 

1. 최솟값을 찾을때는 result ( 최솟값 ) 갱신을 end 갱신 로직에 넣어준다.

2. array[mid] >= target 일때 갱신

 

최댓값을 찾을 때 (Upper Bound)

func findMaximum(_ array: [Int], _ target: Int) -> Int {
    var start = 0
    var end = array.count - 1
    var result = -1
    
    while start <= end {
        let mid = (start + end) / 2
        
        if array[mid] <= target {
            result = mid  // start를 늘릴 때 갱신
            start = mid + 1
        } else {
            end = mid - 1
        }
    }
    
    return result
}

 

1. 최댓값을 찾을때는 result  갱신을 start 갱신 로직에 넣어준다.

2. array[mid] <= target 일때 갱신

 

 

5. 자주 하는 실수와 해결방법

1. 무한 루프

start < end

 

이렇게 하면 특정상황에서 무한루프가 발생하기에 <= 로 하는것을 잊지말것

 

2. mid 오버플로우

(start + end ) / 2 // start + end값이 너무 커서 오버플로우가 일어날 수 있다.
->
start + (end - start) / 2

 

3. 결과값 갱신 시점 혼동

최솟값을 찾을때는 조건을 만족하는 값들 중 가장 작은 값을 찾아야 하기에

array[mid] >= target 

그래야 target이랑 같을 수도있기 때문이다.

> target이면 특정케이스에서 최소를 못찾을지도 모른다.