백준 - 13777.Hunt the rabbit

문제

Mr Farkle was brought up on a farm and spent quite a bit of time in his youth hunting rabbits! He now teaches maths and computing, and came up with a hunting game to help his students learn about the binary search.

He put 50 envelopes at the front of the room, numbered sequentially from 1 to 50. Inside one he hid a rabbit – not a real one, of course, just a card with a rabbit picture on it! He then put cards in all the other envelopes so that if an envelope was chosen with a number lower than the one holding the rabbit, the card would read “Try a higher number”, otherwise the card would read “Try a lower number”.

Students have to find the rabbit using a binary search, and write down the numbers of all the envelopes they open (in order) during their search. Remember, in a binary search you have to pick the middle envelope in the range you are searching. This is easy to find if there is an odd number of envelopes, but with an even number, you have to choose the lower numbered of the two middle envelopes. That means 25 will always be the first envelope checked.

입력

Each line of input will be a single number in the range 1 to 50 inclusive, it being the number of the envelope in which Mr Farkle has hidden the rabbit. The final input will be 0 which should not be processed.

출력

For each line of input, output the numbers of all envelopes opened, in the order they were opened, until the rabbit is found. Each number must be on the same line separated by a space from the previous number.

예제 입력 1 복사

25
17
31
0

예제 출력 1 복사

25
25 12 18 15 16 17
25 38 31

출처

ICPC > Regionals > South Pacific > South Pacific Region > New Zealand Programming Contest > NZPC 2016 G번

알고리즘 분류

• 구현
• 이분 탐색

풀이

이진 탐색 알고리즘을 이용하여 푼다.

주어진 봉투가 10개라고 해보고 찾으려는 값이 8이라고 하면,

1. 10 - 1 = 9 / 2 = 4 + 1 = 5
2. 5는 8이 아니므로
3. 10 - 6 = 4 / 2 = 2 + 6 = 8
4. 타겟넘버를 찾았다

var number = [Int]()
while !number.contains(0) {
    number.append(Int(readLine()!)!)
}

func rabbit() {
    if number[0] == 0 {
        return
    }

    for i in 0 ..< number.count - 1 {
       find(number: number[i])
    }
}

func find(number: Int) {
    var arr = [Int]()
    var max = 50
    var min = 1
    var middle = ((max - min) / 2) + min
    arr.append(middle)

    while true {
        if middle > number {
            max = middle - 1
            middle = ((max - min) / 2) + min
            arr.append(middle)
        } else if middle < number {
            min = middle + 1
            middle = ((max - min) / 2) + min
            arr.append(middle)
        } else {
            for i in arr {
                print(i, separator: " ", terminator: " ")
            }
            print()
            break
        }
    }
}

rabbit()