[Swift] 이진 탐색 구현

[Swift] 이진 탐색 구현

---

조건

1. 배열 내부의 데이터가 정렬되어 있어야 함

2. 탐색 범위를 절반씩 좁혀가며 데이터를 탐색

3. 이진 탐색은 위치를 나타내는 변수를 세 개 사용

-> 시작점, 끝점, 중간점 

-> 중간점으로 찾으려난 데이터와 비교하여 다시 시작점 / 중간점 / 끝점 설정

 

언제 쓰면 좋을까?

- 처리해야 할 데이터의 개수나 값이 1000만 단위 이상으로 넘어갈 때 사용

 

구현

- 재귀 혹은 단순 반복문으로 구현이 가함

- 시간 복잡도: O(logN)

- 아래는 재귀 함수를 호출하는 방식으로 구현

 

func binarySearch(_ array: [Int], _ target: Int, _ count: Int) -> Int {

    if array.count == 1 && array[0] == target {

        return count

    }

    let mid = array.count / 2

    if array[mid] == target {

        return count

    }

    let range = array[mid] > target ? (0..<mid) : (mid+1..<array.count)

    return binarySearch(Array(array[range]), target, count+1)

}