1. 이진 탐색 개요
이진 탐색(Binary Search)은 정렬된 배열에서 특정 값의 위치를 찾는 알고리즘입니다.
이진 탐색은 배열을 절반으로 나누어 원하는 값을 찾기 때문에 매우 효율적이며,
평균 및 최악의 경우 모두 O(log n)의 시간 복잡도를 가집니다.
이는 선형 탐색(Linear Search)의 O(n)보다 훨씬 우수합니다.
1.1 이진 탐색의 원리
이진 탐색은 다음과 같은 절차로 진행됩니다:
- 탐색할 배열이 정렬되어 있는지 확인합니다.
- 시작 인덱스와 끝 인덱스를 설정합니다.
- 중간 인덱스를 계산합니다.
- 중간 값과 찾고자 하는 값을 비교합니다.
- 찾고자 하는 값이 중간 값보다 작으면 끝 인덱스를 중간 인덱스 – 1로,
크면 시작 인덱스를 중간 인덱스 + 1로 설정합니다. - 값을 찾거나 시작 인덱스가 끝 인덱스보다 클 때까지 반복합니다.
2. 알고리즘 문제
이제, 이진 탐색을 활용한 문제를 살펴보겠습니다.
문제: 숫자 배열에서 특정 숫자의 인덱스 찾기
주어진 정수 배열nums와 정수target가 주어질 때,target이 배열nums에 존재하면 해당 인덱스를 반환하고, 존재하지 않으면 -1을 반환하는 함수를 작성하세요. 예시: 입력: nums = [-1,0,3,5,9,12], target = 9 출력: 4 입력: nums = [-1,0,3,5,9,12], target = 2 출력: -1
3. 문제 풀이 과정
문제를 풀기 위해 이진 탐색 알고리즘을 사용하여 배열에서 target 값을 찾겠습니다.
단계별로 설명하겠습니다.
3.1 함수 정의
먼저, 이진 탐색을 수행할 binarySearch 함수를 정의합니다.
이 함수는 배열 nums와 target 값을 인자로 받습니다.
func binarySearch(nums: [Int], target: Int) -> Int {
var left = 0
var right = nums.count - 1
while left <= right {
let mid = left + (right - left) / 2
if nums[mid] == target {
return mid
} else if nums[mid] < target {
left = mid + 1
} else {
right = mid - 1
}
}
return -1
}
3.2 변수 초기화
변수 left와 right를 각각 0과 배열의 길이 – 1로 초기화합니다.
left는 탐색 범위의 시작 인덱스를, right는 끝 인덱스를 나타냅니다.
3.3 중간값 계산
while 루프를 사용하여 left가 right보다 작거나 같을 때까지 반복합니다.
매 반복에서 중간 인덱스인 mid를 계산합니다.
이때 left + (right - left) / 2를 사용하여 중간값을 계산하면 오버플로우를 방지할 수 있습니다.
3.4 타겟 비교
중간값 nums[mid]가 target과 같으면 해당 인덱스 mid를 반환합니다.
만약 nums[mid]가 target보다 작으면,
left를 mid + 1로 설정하여 오른쪽 절반을 탐색합니다.
반대로 nums[mid]가 target보다 크면,
right를 mid - 1로 설정하여 왼쪽 절반을 탐색합니다.
3.5 결과 반환
반복이 종료되면 target가 배열에 존재하지 않는 것이므로 -1을 반환합니다.
4. 전체 코드
func binarySearch(nums: [Int], target: Int) -> Int {
var left = 0
var right = nums.count - 1
while left <= right {
let mid = left + (right - left) / 2
if nums[mid] == target {
return mid
} else if nums[mid] < target {
left = mid + 1
} else {
right = mid - 1
}
}
return -1
}
// 사용 예
let nums = [-1, 0, 3, 5, 9, 12]
let target = 9
let result = binarySearch(nums: nums, target: target)
print(result) // 4
5. 이진 탐색의 장점과 단점
5.1 장점
이진 탐색의 주요 장점은 빠른 검색 속도입니다.
매우 큰 데이터셋을 다루는 경우 선형 검색에 비해 월등히 높은 성능을 보입니다.
5.2 단점
그러나 이진 탐색을 사용하기 위해서는 데이터가 정렬되어 있어야 하는 단점이 있습니다.
데이터 삽입과 삭제가 빈번한 경우 별도의 정렬 작업이 필요할 수 있습니다.
6. 결론
이진 탐색은 효율적인 검색 방법으로, 코딩 테스트에서 자주 출제되는 주제 중 하나입니다.
위의 문제를 통해 이진 탐색의 원리와 구현 방법을 이해하고,
스위프트로 코드를 작성하는 과정에서 유용한 경험을 얻으셨기를 바랍니다.
7. 추가 연습 문제
이진 탐색을 더 깊이 이해하기 위해 아래의 추가 문제를 풀어보세요.
- 주어진 정수 배열에서 특정 숫자가 등장하는 모든 인덱스를 찾아 반환하는 함수를 작성하세요.
- 정렬된 배열의 첫 번째와 마지막 위치를 찾아주는 함수를 구현하세요.
- 정수 배열에서 두 개의 수를 더하여 특정 숫자를 만드는 조합이 있는지를 판단하는 함수를 작성하세요.