[Swift] - 이분탐색

Swift로 이분탐색을 구현해보자

1. 문제 설명

자연수의 배열이 주어지면, 오름차순으로 배열한 뒤, 숫자 n 이 몇번 째 index 인지 구하라...

2. 나의 풀이

import Foundation

func solution(_ n: [Int], _ m: Int) -> Int {
    
    return n.sorted().firstIndex(of: 32)!
}

스위프트에는 너무나도 편한,, sorted() 라는 기능과 firstIndex(of: ?) 라는 기능이 있기에 아주 쉬운 코드였다. 하지만 수업을 들으며 아주 비효율적인 코드라는 것을 알게 되었다. 이유는 아래에서 설명한다.

3. 더 좋은 풀이

이분검색이란?

말그대로 중앙을 나눈다. 내가 찾는 값이 중앙이 될 때 까지..

1, 2, 3, 4, ...... 십만 의 배열이 있다고 하자.
나는 2733 을 찾고 싶다. 물론 여기선 답이 2732 라는 것을 알고 있다.

이분검색을 이용해 찾자면, 십만의 반을 나눈다. 1~ 5만, 5만 ~ 10만
2733은 전자에 속한다.

1~ 5만을 또 2로 나눈다. 1~ 2만5천, 2만5천 ~ 5만

역시 전자에 속한다

1~ 12500, 12500 ~ 25000 -> 1~ 6250 -> 3125 ....

코드로 구현해보자.

import Foundation

func solution(_ n: [Int], _ m: Int) -> Int {
    var num = n.sorted()
    var i: Int = n.count - 1
    var left: Int = 0
    var right: Int = n.count - 1
    while true {
        if num[(left+right)/2] == m {
            return (left+right)/2
        } else if m < num[(left+right)/2] {
            right = (left+right)/2
        } else {
            left = (left+right)/2
        }
    }
}

left 와 right 를 놓고 while 문을 돌린다.
left+ right / 2 보다 우리가 원하는 숫자가 작다면, right 을 left+ right/2 로 바꾼다.
반대로 더 크다면, left 를 left+right/.2 로 바꾼다.

결국 원하는 숫자는 찾아질 수밖에없다.

삼분검색 사분검색도 구현해 볼 수 있을 것 같다.