[DataStructure / Algorithm] Binary Search

전성훈·2023년 11월 9일

Algorithms datastructure swift

Data Structure-Algorithm

목록 보기

17/35

주제: 정렬된 배열에서 효율 좋은 탐색

이진 탐색이란

이진 탐색은 O(log n)의 시간 복잡도를 가진 가장 효율적인 탐색 알고리즘 중 하나이다.
이것은 균형 잡힌 Binary Search Tree에서 요소를 검색하는 것과 유사하다.
이진 탐색을 사용하기 전에 두 가지 조건이 충족되어야 한다.
1. 컬렉션 요소의 접근 시간이 상수시간이어야 하기 때문에 RandomAccessCollection 프로토콜을 준수해야 한다.
2. 컬렉션은 정렬되어야 한다.
Swift의 Array 타입은 검색하기에 firstIndex(of: ) 메서드를 활용한다. 이는 전체 컬렉션을 첫 번째 요소를 찾을 때까지 순회한다. 그렇기 때문에 최악의 경우 O(n)의 시간 복잡도를 나타낸다.
Array가 이미 정렬되어있다는 것을 알고있다면 이진 탐색을 활용하면 좋다.
1. 중간 인덱스를 확인한다.
2. 찾고자 하는 값과 일치하면 인덱스를 반환하고 아니면 다음 순서를 진행한다.
3. 중간 인덱스 기준 작으면 왼쪽, 크면 오른쪽 시퀀스만 고려한다. 이를 값을 찾을 때 까지 반복한다.
이진 탐색은 프로그래밍 면접에서 자주 출제되는 유형 중 하나이다. "정렬된 배열이 주어졌을 때.."와 같은 내용이 주워지면 충분히 이진 탐색을 고려해 볼만하다.

구현

재귀 함수를 활용한 이진 탐색

RandomAccessCollection을 준수한 배열에 바로 사용하는 방법

public extension RandomAccessCollection where Element: Comparable {
	func binarySearch(for value: Element, in range: Range<Index>? = nil) -> Index? { 
		let range = range ?? stratIndex..<endIndex
		
		guard range.lowerBound < range.upperBound else { 
			return nil
		}
		let size = distance(from: range.lowerBound, to: range.upperBound)
		let middle = index(range.lowerBound, offsetBy: size/2)
		
		if self[middle] == value { 
			return middle
		} else if self[middle] > value { 
			return binarySearch(for: value, in: range.lowerBound..<middle)
		} else { 
			return binarySearch(for: value, in: index(after: middle)..<range.upperBound)
		}
	}
}

Int형 배열에서 반복문을 활용한 이진 탐색

func binarySearch(_ array: [Int], _ target: Int, _ startIndex: Int, _ endIndex: Int) -> Int? { 
	var startIndex = startIndex 
	var endIndex = endIndex 
	while startIndex <= endIndex { 
		let mid = (startIndex + endIndex) / 2 
		
		if array[mid] == target { 
			return mid
		} else if array[mid] > target { 
			endIndex = mid - 1 
		} else { 
			startIndex = mid + 1
		}
	}
	return nil 
}

활용 코드

let array = [1, 5, 15, 17, 19, 22, 24, 31, 105, 150]
let search31 = array.firstIndex(of: 31)
let binarySearch31 = array.binarySearch(for: 31)
let binartSearch31_2 = binarySearch(array, 31, 0, array.count - 1)

print("firstIndex: \(String(describing: search31))")
print("binarySearch: \(String(describing: binarySearch31))")
print("binartSearch_2 : \(binartSearch31_2)")

firstIndex: Optional(7)
binarySearch: Optional(7)
binartSearch_2 : Optional(7)