[Algorithm] Binary Search, 이진 탐색

What is it

이진 탐색 알고리즘(binary search algorithm)은 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다.
정렬된 리스트의 중간 값을 임의로 선택해, 그 값과 찾고자 하는 값의 대소를 비교하는 방식이다.
반복문 혹은 재귀용법을 사용해서 구현할 수 있다.

검색 원리상 정렬된 리스트에만 사용할 수 있다는 단점이 있지만, 검색이 반복될 때마다 목표값을 찾을 확률은 두 배가 되므로 속도가 빠르다는 장점이 있다.

How to work

오름차순으로 정렬된 리스트에서 진행된다.

• 분할(Divide)
  • 리스트를 중간값을 기준으로 두개의 서브 리스트로 나눈다.
• 정복(Conquer)
  • 검색할 숫자 < 중간값 이면, 앞 부분의 서브 리스트에서 검색할 숫자를 찾는다.
  • 검색할 숫자 > 중간값 이면, 뒷 부분의 서브 리스트에서 검색할 숫자를 찾는다.
  • 검색할 숫자 == 중간값 이면, 해당 값 혹은 true 리턴.

Let's make it Code

func binarySearch(_ array: [Int], _ target: Int) -> Bool {
    if array.count == 1, array[0] == target { return true }
    if array.count == 1, array[0] != target { return false } 	//#1
    
    let medium = array[array.count / 2]		//#2
    
    if medium < target {		//#3
       return binarySearch(Array(array[medium...]), target)
    }else if medium > target {
        return binarySearch(Array(array[..<medium]), target)
    }else if medium == target {
        return true
    }
    
    return false
}

let arr = [2,3,4,5,6,7]

print(binarySearch(arr, 4))

#1
남은 원소가 1이고 찾는 값과 같다면 true
남은 원소가 1이지만 찾는 값과 다르다면 false 리턴

#2
배열의 중간값으로 비교할 기준값 삼음

#3
중간값과 찾는 값 비교해서 재귀 호출해서 찾음

Algorithm Analysis

n개의 리스트를 매번 2로 나누어 1이 될때까지 비교 연산을 k번 진행한다고 했을 때,
빅오 표기법으로는 k + 1이 결국 최종 시간 복잡도이다. (1이 되었을때도, 비교 연산을 한 번 수행하므로)
결국 O(logn + 1)이고 상수는 삭제되므로 O(logn)

References

• https://ko.wikipedia.org/wiki/이진_검색_알고리즘