[swift] 정렬 함수를 사용하여 이진 탐색 구현하기
이진 탐색(binary search)은 정렬된 배열에서 특정 원소를 찾는 알고리즘입니다. 이진 탐색을 구현하기 위해서는 정렬된 배열과 찾고자 하는 원소를 이용해야 합니다.
Swift의 정렬 함수(sort)를 사용하여 배열을 정렬하고, 이진 탐색 함수를 구현해보겠습니다.
정렬 함수를 사용하여 배열 정렬하기
Swift에서는 배열을 정렬하기 위해 내장된 정렬 함수(sort)를 제공합니다. 이 함수를 사용하면 간단하고 효율적으로 배열을 정렬할 수 있습니다.
다음은 정수 배열을 오름차순으로 정렬하는 예제 코드입니다.
var numbers = [5, 2, 8, 1, 3]
numbers.sort() // [1, 2, 3, 5, 8]
정렬된 배열을 이용하여 이진 탐색을 구현해보겠습니다.
이진 탐색 함수 구현하기
이진 탐색 함수는 찾고자 하는 원소가 배열의 중간에 위치하는지를 확인하고, 중간 값과 비교하여 탐색을 진행합니다. 만약 찾고자 하는 원소가 중간 값보다 작다면, 중간 값을 기준으로 왼쪽 부분 배열을 탐색하고, 반대의 경우에는 오른쪽 부분 배열을 탐색합니다. 이 과정을 재귀적으로 반복하여 원소를 찾습니다.
다음은 Swift로 구현한 이진 탐색 함수의 예제 코드입니다.
func binarySearch<T: Comparable>(array: [T], target: T) -> Int? {
var lowerBound = 0
var upperBound = array.count - 1
while lowerBound <= upperBound {
let midIndex = (lowerBound + upperBound) / 2
let midValue = array[midIndex]
if target == midValue {
return midIndex
} else if target < midValue {
upperBound = midIndex - 1
} else {
lowerBound = midIndex + 1
}
}
return nil
}
let numbers = [1, 2, 3, 5, 8]
if let index = binarySearch(array: numbers, target: 3) {
print("원소가 \(index)번째에 있습니다.")
} else {
print("원소를 찾을 수 없습니다.")
}
결론
Swift의 내장된 정렬 함수와 이진 탐색 알고리즘을 활용하여 배열에서 원소를 찾는 방법을 알아보았습니다. 이진 탐색은 정렬된 배열에서 효율적으로 원소를 찾을 수 있는 알고리즘이므로, 배열을 정렬한 뒤 이진 탐색을 사용하여 필요한 원소를 찾을 수 있습니다.