[스위프트:알고리즘] 이진 탐색[2 / 3]: Binary Search: 이진 탐색: 반복문, 재귀호출로 구현하기

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 매개변수는 배열 인스턴스 array 와, 찾고자 하는 값인 value
public func binarySearch_for (array: [Int],for value: Int) -> Int? {
    var startIndex = 0 // 매개변수 배열의 첫 번째 인덱스
    var endIndex = array.count - 1 // 배열의 마지막 인덱스
    // array.endIndex 로 설정하면 array 가 동적으로 변하게 되므로 오류남을 주의
    while startIndex <= endIndex { // 원하는 값 못찾았을 때 종료조건
        let middleIndex = (startIndex + endIndex) / 2 // 중간 인덱스 
        if value == array[middleIndex]{
            return middleIndex // 값 찾았을 때 종료조건
        } else if array[middleIndex] > value { // 왼쪽 탐색
            endIndex = middleIndex - 1 // 뒷쪽 인덱스 값 변화줌.
        } else if array[middleIndex] < value { // 오른쪽 탐색
            startIndex = middleIndex + 1 // 앞쪽 인덱스 값 변화줌
        }
    }
    return -1 // 찾고자 하는 값이 없을 때 while 문이 종료되므로 -1 반환하도록 설정
}
Colored by Color Scripter
cs

코드 분석

전체적으로 중간값을 찾고 찾으려는 값과 중간값을 비교하는 로직의 반복이지?
반복문에서 입력값의 변화는 startIndex 혹은 endIndex 를 주어서 찾으려는 값의 범위를 점점 줄여가고 있지? ( 재귀호출의 원칙이기도 함. )
종료조건은 2 가지 경우가 있지?

원하는 값을 찾았을 때 ( value == array[middleIndex] 일 때 )
원하는 값을 찾지 못했을 때 ( startIndex <= endIndex 에서 범위 벗어나서 반복 종료하게 됨. )

난 원하는 값을 찾지 못했을 때의 종료조건을 생각하지 못해서 계속 오류가 났었어.

재귀호출로 구현한 이진 탐색

반복문에서 보다 확장해서 특정 범위까지 매개변수에서 설정할 수 있도록 해보자~

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 매개변수에는 배열과 찾고자하는 값에 더해서 찾으려는 범위까지 입력 가능.
public func binarySearch_recur (array: [Int],
                                for value: Int,
                                startIndex: Int? = nil,
                                endIndex: Int? = nil) -> Int? {
    var startIndex = startIndex ?? 0 // ?? 키워드는 startIndex 가 옵셔널이면 강제해제 하고 nil 이면 0 을 대입하라는 뜻
    var endIndex = endIndex ?? array.count - 1
    var middleIndex: Int {
        return (startIndex + endIndex) % 2 == 0 ? (startIndex + endIndex) / 2 : (startIndex + endIndex + 1) / 2 
        // 특정 범위를 입력해 주었을 때 두 인덱스의 값이 홀수일 때 인덱스가 하나 작아지므로 바꿔주고
    }
    guard startIndex <= endIndex else { return -1 } // 원하는 값 못찾았을 때 종료조건
    if value == array[middleIndex] { // 원하는 값 찾았을 때 종료조건
        return  middleIndex
    } else if array[middleIndex] > value { // 왼쪽 탐색
        endIndex = middleIndex - 1 // 뒷쪽 인덱스 변화줘서 재귀호출
        // 재구호출은 문제의 범위가 작은 방향으로 이동해야 한다는 원칙이 적용되는 부분
        return binarySearch_recur(array: array, for: value, startIndex: startIndex, endIndex: endIndex)
    } else if array[middleIndex] < value { // 오른쪽 탐색
        startIndex = middleIndex + 1 // 앞쪽 인덱스 변화줘서 재귀호출
        return binarySearch_recur(array: array, for: value, startIndex: startIndex, endIndex: endIndex)
    } else { return -1 }
}
Colored by Color Scripter
cs

코드 분석

반복문 에서와 전체적인 틀은 같아.
매개변수 startIndex , endIndex 초기값이 nil 로 기본값이 설정되 있음.

특정 인덱스를 매개변수에서 설정하지 않으면 ?? 키워드를 이용해서 startIndex 는 0, endIndex 는 array.count - 1 로 설정해줌

재귀호출의 원칙 모른다면 여기

1. 문제의 범위는 작은 방향으로 이동해야 한다. -> startIndex 와 endIndex 가 변화하면서 범위가 좁아지지?
2. 종료조건이 있어야 한다. -> 반복문에서와 마찬가지고 2가지 경우의 종료조건 있지?

실행과 결과

전체 소스 코드

'스위프트: Swift > 알고리즘 : Algorithms in Swift' 카테고리의 다른 글

[스위프트:알고리즘] 이진 탐색[3 / 3]: Binary Search: 이진 탐색: 프로토콜 지향으로 구현하기 (0)	2018.10.16
[스위프트:알고리즘] 이진 탐색[1 / 3]: Binary Search: 이진 탐색이 뭐야? (0)	2018.10.16
[스위프트 : 알고리즘] 재귀 : 최대공약수 (6 / 6) : GCD: 재귀호출: 재귀함수: 반복문: 팩토리얼: 거듭제곱: 피보나치: 하노이의 탑: 최대공약수 (0)	2018.10.04
[스위프트 : 알고리즘] 재귀 : 하노이의 탑 (5 / 6) : Hanoi: 재귀호출: 재귀함수: 반복문: 팩토리얼: 거듭제곱: 피보나치: 하노이의 탑: 최대공약수 (0)	2018.10.04
[스위프트 : 알고리즘] 재귀 : 피보나치 수열(4 / 6) : Fibonacci: 재귀호출 : 재귀함수: 반복문: 팩토리얼: 거듭제곱: 피보나치: 하노이의 탑: 최대공약수 (0)	2018.10.04

인기포스트 MORE POST

ABOUT ME

씩이 머릿속 씩이 머릿속

'스위프트: Swift > 알고리즘 : Algorithms in Swift' 카테고리의 다른 글

티스토리툴바

인기포스트 MORE POST

ABOUT ME

'스위프트: Swift > 알고리즘 : Algorithms in Swift' 카테고리의 다른 글

관련글 관련글 더보기

티스토리툴바