[Swift][이진탐색] 백준 1920번 (수 찾기)

요구능력 : 이진탐색

 

코드설명 : 

 

수를 브루트포스로 찾는다는 생각을 할 수도 있다.

하지만 문제에서 정수의범위가 어마어마하게 크기 때문에 브루트포스를 사용하면 시간초과가난다.

이럴때 생각할 수 있는게 이진탐색(BinarySearch)이다. 카테고리에 이분탐색이라고 적혀있...

 

1. 이진탐색을 하기위한 배열을 정렬해준다.

그래야 시작, 중간, 끝값을 이용해서 이진탐색이 가능하다.

 

2. start값은 맨 처음부터 시작해야하기 때문에 초기에는 0을 삽입해준다.

end 값은 맨 뒤부터 시작해야하기 때문에 초기에는 [배열의 크기 - 1]만큼 삽입해준다.

 

3. start값이 end값을 넘어간다면 없는 목표한 target이 없는 것이므로 멈춰주도록 조건을 설정해준다.

 

4. mid값은 소수점을 버린 start와 end의 중간값이다. (중간값이 4.5이면 필요한건 4이다.) 

 

5. 탐색의 중간값(firstArr[mid])이 목표값(target)과 같으면 성공이므로 문제 조건에 따라 1을 리턴한다.

 

6. 탐색의 중간값(firstArr[mid])이 목표값보다 크면 뒤의 절반을 볼 필요가 없으므로 탐색의 끝을 중간보다 한칸앞에 위치시킨다.

 

7. 탐색의 중간값(firstArr[mid])이 목표값보다 작으면 앞의 절반을 볼 필요가 없으므로 탐색의 시작을 중간보다 한칸앞에 위치시킨다. 

 

8. 위에 적혀있는대로 반복했는데도 start값이 end값을 넘어간다면 목표값이 없다는 의미이므로 문제대로 0을 리턴해준다.

 

후기 :  이진탐색을 처음 접근하는 사람들에게 아주 좋은문제인것같다,,

 

let n = Int(readLine()!)!
var firstArr = readLine()!.split(separator: " ").map{Int($0)!}

let m = Int(readLine()!)!
var secondArr = readLine()!.split(separator: " ").map{Int($0)!}

firstArr.sort()

func binarySearch(_ arr: [Int], _ target: Int) -> Int{
    var start = 0
    var end = arr.count - 1

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


for i in 0..<m {
    print(binarySearch(firstArr, secondArr[i]))
}