Binary Search
- Binary Search는 seraching algorithm 중 가장 효율적인 알고리즘 중 하나이다 → 시간복잡도가 O(logn)이기 떄문.
- 정렬된 배열이나 리스트에서 특정 값을 빠르게 찾기 위한 알고리즘이다. 매번 중간값과 비교해, 찾고자 하는 값이 중간값보다 크면 오른쪽 절반을, 작으면 왼쪽 절반을 탐색하는 방식으로 진행된다.
이진 검색을 사용하기위해 충족해야 하는 조건
-
O(1) 시간 안에 index manipulation 수행이 가능해야 한다. →
RandomAccessCollection컬렉션이어야 한다O(1) 시간 내에 특정 인덱스와 값에 접근이 가능해야 한다
ex. array , array 기반 리스트
- 컬렉션은 정렬되어 있어야 한다.
Binary Search 수행하는 과정
만약 배열에서 31을 찾는다고 하면 8번의 과정을 거쳐서 찾는다. 그렇다면 이진탐색을 활용한다면 어떨까?
Step 1. middle index를 찾는다.
컬렉션의 중간 인덱스를 찾는다.
Step 2. middle index의 element를 체크한다.
- step 1 에서 찾았던 middle index의 value를 체크한다.
- 이게 만약 내가 찾는 값이라면 바로 index를 반환한다.
- 아니라면 step 3 를 진행한다.
Step 3. 재귀적으로 이진 탐색을 호출한다.
- step 2에서 원하는 값을 찾지 못하면, 이진탐색을 재귀적으로 호출한다. 단,
- 찾고자 하는 값이 middle value보다 작으면, 찾는 범위의 닫는 범위는 index 0부터 middle index 까지가 될 것이다.
- 찾고자 하는 값이 middle value보다 크면, 찾는 범위의 여는 범위는 middle index 부터 끝까지가 될 것이다.
- 이를 반복해서 범위는 1/2 씩 계속 줄이다보면 결국 원하는 값을 찾는데 걸리는 시간복잡도는 O(logn)이 되는 것.
구현
RandomAccessCollection
public extension RandomAccessCollection where Element: Comparable {
func binarySearch(for value: Element, in range: Range<Index>? = nil) -> Index? {
// 1 : range의 nil check 진행한다.
// 만약 nil이라면, 전체 컬렉션 범위가 들어온다.
let range = range ?? startIndex..<endIndex
// 2 : 유효한 range 인지 체크하고, 유효하지 않으면 nil 반환
guard range.lowerBound < range.upperBound else {
return nil
}
// 3 : 중간 index 찾기
let size = distance(from: range.lowerBound, to: range.upperBound)
let middle = index(range.lowerBound, offsetBy: size / 2)
// 4 : 중간값이 찾고 있는 값이면 해당 값 반환
if self[middle] == value {
return middle
// 5. 아니고, value보다 middle 값이 크면
// value가 왼쪽에 있다는 거니까 왼쪽을 다시 찾는다 (재귀로)
} else if self[middle] > value {
return binarySearch(for: value, in: range.lowerBound..<middle)
// 반대의 경우, 오른쪽을 다시 찾는다 (재귀)
} else {
return binarySearch(for: value, in: index(after: middle)..<range.upperBound)
}
}
}언제 사용하면 좋을까?
주어진 정렬된 배열...의 조건이 문제에 주어지는 경우- 의 시간복잡도가 걸릴것으로 보이는 탐색 문제에서 이진 탐색을 사용해서 O(nlogn) 까지 줄여볼 수 있다.
Binary Search Challenge
1. Implementation with free function
- free function은 특정 클래스나 구조체에 속하지 않고, 독립적으로 동작하는 함수이다.
func binarySearch<T: comparable>(_ array: [T], key: T) -> Int? {
var low = 0
var high = array.count - 1
while low <= high {
let mid = (high + low) / 2
if array[mid] == key {
return mid
} else if array[mid] < key {
low = mid + 1
} else {
high = mide - 1
}
}
return nil
}2. Searching for a range
Write a function that searches a sorted array and that finds the range of indices for a particular element.
For example:
let array = [1, 2, 3, 3, 3, 4, 5, 5]
findIndices(of: 3, in: array)
findIndices should return the range 2..<5, since those are the start and end indices for the value 3.
처음 작성한 코드
// array가 주어질 때,
// 특정 value가 있는 인덱스의 범위를 출력하기
func findIndices(of value: Int, _ array: [Int]) -> Range<Int> {
// value가 arry의 어디서 시작하는지 체크해야한다.
// 배열을 그냥 순회하면 O(n*value.count) 만큼 들겠지?
// 그럼 ... 시작하는 range를 찾는 함수가 필요할거고
// 끝나는 range를 찾는 함수가 필요할 것이다.
func findStartIndex(of value: Int, _ array: [Int]) -> Int {
// 중간값을 찾는다.
// 중간값에 있는 값이 value와 같으면, 왼쪽에 더 있을 수 있으니까
// 왼쪽 절반 범위에서 다시 찾기
var low = 0
var high = array.count - 1
var mid = (low + high) / 2
while low <= high {
if value == array[mid] {
if value != array[mid - 1] {
return mid
} else {
high = mid - 1
}
} else if value < array[mid] {
if value == array[mid + 1] {
return mid
} else {
high = mid - 1
}
}
}
return -1
}
func findEndIndex(of value: Int, _ array: [Int]) -> Int {
var low = 0
var high = array.count - 1
var mid = (low + high) / 2
while low <= high {
let mid = (low + high) / 2
if value == array[mid] {
if value != array[mid + 1] {
return mid
} else {
low = mid + 1
}
} else if value > array[mid] {
if value == array[mid - 1] {
return mid - 1
} else {
low = mid + 1
}
}
}
return -1
}
let start = findStartIndex(of: value, array)
let end = findEndIndex(of: value, array)
return Range(start...end)
}
위 코드에서의 오류
-
mid 값을 업데이트 하지 않았다. (high, low 값이 변할 때 마다 mid 값도 바뀌기 때문에 재계산을 해줘야 하는데, 그걸 해주지 않았다.)
-
경계체크에서 오류가 있었다
-
나는 value가 mid 값과 동일할 때,
array[mid-1]이나array[mid+1]을 하기 전 경계체크가 필요했는데 이를 하지 않아서 index out of range 오류를 발생시켰다. -
이 부분은 일단 해당 mid 값을 result 에 넣어놓고, 추가로 high = mid - 1 로 mid 이전에도 해당 value가 있는지 체크하는 방식으로 수정해서 해결한다.
-
이러면 굳이 경계체크를 매번 하지 않고도 중복된 값이 있을 경우를 확인할 수 있다.
수정된 코드
func findIndices(of value: Int, in array: [Int]) -> Range<Int> {
func findStartIndex(of value: Int, _ array: [Int]) -> Int {
// 중간값을 찾는다.
// 중간값에 있는 값이 value와 같으면, 왼쪽에 더 있을 수 있으니까
// 왼쪽 절반 범위에서 다시 찾기
var low = 0
var high = array.count - 1
var mid = (low + high) / 2
var result: Int? = nil
while low <= high {
let mid = (high + low) / 2
if value == array[mid] {
result = mid
high = mid - 1
} else if value > array[mid] {
low = mid + 1
} else {
high = mid - 1
}
}
guard let result = result else { return -1 }
return result
}
func findEndIndex(of value: Int, _ array: [Int]) -> Int {
var low = 0
var high = array.count - 1
var mid = (low + high) / 2
var result: Int? = nil
while low <= high {
let mid = (low + high) / 2
if value == array[mid] {
result = mid
low = mid + 1
} else if value > array[mid] {
high = mid - 1
} else {
low = mid + 1
}
}
guard let result else { return -1}
return result
}
let start = findStartIndex(of: value, array)
let end = findEndIndex(of: value, array)
return Range(start...end)
}회고
-
지금 공부하고 있는 "Data Structures and Algorithms in Swift ver 5.0" 책에서는 단순히 자료구조 및 알고리즘의 구현방법 및 특성을 나열하는게 아니라, 왜 해당 자료구조가 필요한지 그 필요성과 중요성에 대해 깨달으며 공부할 수 있게 해 정말 도움이 된다.
-
특히 Challenge 문제들로 대표 유형을 분석하고, 왜 앞서 배운 자료구조를 적용해야 하는지를 알 수 있어 암기식이 아닌, 합리적으로 받아들일 수 있었다. 매번 반복되는 알고리즘 공부지만 이번에는 깨닫는게 사뭇 다르다고 느끼고 있다.
