1. 이진 탐색(Binary Search)
Binary Search
•
탐색 : 특정 값을 찾는 알고리즘
•
이진 탐색 : 정렬되어 있는 값들 중에서 특정 값을 찾는 알고리즘
•
찾고자 하는 값과 중간 값을 비교하여 탐색 공간을 절반씩 제거할 수 있습니다.
•
탐색할 숫자를 절반씩 지워나가기 때문에 O(log n)의 시간 복잡도를 가지게 됩니다.
•
이미 정렬되어 있다면, 이진 탐색이 굉장히 효율적이고, 정렬을 다시 하더라도 숫자를 엄청 많이 탐색해야 하는 경우에도 효율적이라고 말할 수 있겠습니다. → 정렬하고 이진 탐색할 경우 O(n log n)의 시간복잡도를 가지게 됩니다.
2. 이진 탐색의 구현
Tip
•
탐색하고자 하는 원소들이 이미 정렬되어 있다고 가정합니다.
•
재귀함수를 이용하여 구현할 수도 있고, 단순 반복문을 통해 구현할 수도 있습니다.
•
재귀함수 : binarySearch(array, start, end, value) // array의 start번째 값 부터 end번째 값 중 value를 찾는 함수
•
단순 반복문 : 투 포인터(start, end)를 활용하여 구현할 수 있습니다.
func binarySearch(_ array: [Int], _ start: Int, _ end: Int, _ value: Int) -> Bool {
if start >= end {
return array[start] == value ? true : false
}
let mid: Int = (start + end) / 2
if array[mid] == value {
return true
}
return array[mid] < value ? binarySearch(array, mid + 1, end, value) : binarySearch(array, start, mid - 1, value)
}
Swift
복사
3. 매개 변수 탐색(Parametric Search)
Parametric Search
•
Binary Search를 이용하여 문제를 해결하는 방법입니다.
•
원래의 값들을 대신할 수 있는 매개변수들이 정렬되어 있는 경우 사용할 수 있습니다.
•
원래의 값들을 통해 매개 변수를 구하기 위한 별도 작업이 필요합니다.