이분 탐색 ( Binary Search / Swift ) - 1

 이분 탐색은 정렬된 데이터에서 값을 빠르게 찾는 방법 중 하나입니다.

 

var nums: [Int] = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

view raw Binary_Search_1.swift hosted with ❤ by GitHub

일반적인 방법으로 위와 같은 Int 배열에서 "9" 를 찾는다고 가정하면, O(n) 시간 복잡도를 가집니다. 

nums.enumerated().compactMap { $0.element == 9 ? $0.offset : nil } // 최대 O(n)

view raw Binary_Search_2.swift hosted with ❤ by GitHub

 

이분 탐색은 첫 인덱스가 아닌 중간부터 값을 비교하여 탐색할 구간을 정합니다.

	var end: Int = nums.count
	while (start <= end) {
	var mid: Int = (start + end) / 2
	if nums[mid] == 9 {
	print(mid)
	break
	}
	else if nums[mid] < 9 {
	start = mid + 1
	}
	else {
	end = mid - 1
	}
	}

view raw Binary_Search_3.swift hosted with ❤ by GitHub

 

start, mid, end 가 기준점이 되어 구간을 선택하고, 필요 없는 구간은 탐색하지 않기 때문에,

 

O(logN) 의 시간 복잡도를 가집니다. 

 

 

 

주의점으로는 "정렬되어 있는 데이터" 에서만 사용이 가능하다는 점입니다.

 

 

비정렬된 상태에서 사용될 때 정렬 알고리즘 + 이분 탐색 방법이 더 효율적일지,

 

혹은 선형 탐색 알고리즘이 더 나을지는 개발자의 판단이 필요합니다.

 

 

 

 

다음으로는 이분 탐색의 활용으로 파라메트릭서치(Parametric Search) 와

 

상한, 하한선 (Lower Bound, Upper Bound) 에 대해 포스팅하겠습니다.