iOS) 이진탐색 정리 및 실제 구현

 

이진 탐색(Binary Search)

분할정복 방식을 사용하여, 매 단계에서 탐색 범위를 반으로 줄여나가며 특정 값을 찾아내는 알고리즘

정렬된 배열에만 적용 가능하기 때문에, 이진 탐색을 수행하기 전에 배열이 정렬되어 있어야 한다.

시간복잡도 : O(logN)

 

1. 초기화 : 탐색 시작 전, 검색 범위를 배열의 전체로 설정

- 최소 인덱스 low(임의의 변수이름)를 0으로, 최대 인덱스를 배열의 마지막 인덱스 high(임의의 변수이름)로 설정

2. 중앙 요소 확인 : 배열의 중앙 요소를 찾는다.

- (최소 인덱스 + 마지막 인덱스) / 2가 중앙 요소의 인덱스일 것이다.

3. 조건 판단

- 중앙 요소가 찾고자 하는 값과 같다면, 탐색을 종료하고 그 위치를 반환

- 중앙 요소가 찾는 값보다 크다면, 찾는 값은 중앙 요소의 왼쪽에 있음. high를 중앙 요소 바로 이전 인덱스로 변경

- 중앙 요소가 찾는 값보다 작다면, 찾는 값은 중앙 요소의 오른쪽에 있음. low를 중앙 요소의 바로 다음 인덱스로 변경

4. 반복 또는 종료

- 새로운 low, high를 바탕으로 2번 과정으로 돌아가 원하는 값을 얻을 때까지 탐색을 반복한다.

- low > high가 된다면, 배열 내에 찾는 값이 존재하지 않음을 의미하며, 탐색을 종료한다.

 

 

이진 탐색을 이용하여, 특정 수의 제곱근을 구하는 메서드 구현

 

func getSquareRoot(_ x: Double, precision: Double = 0.00001) -> Double {
    var low: Double = 0
    var high: Double = max(1, x) // x가 1보다 작은 경우를 처리하기 위해 max 함수 사용
    var mid: Double = 0
    
    if x == 0 || x == 1 {
    	return x
    }

    while low <= high {
        mid = (low + high) / 2
        let square = mid * mid

        if abs(square - x) <= precision { //정밀도 조건을 만족하면 리턴
            return mid
        } else if square < x {
            low = mid + precision
        } else {
            high = mid - precision
        }
    }

    return mid
}

정밀도를 고려해서 구현한 코드

0.00001을 기본값으로 지정했으며, 필요한 경우 이 값을 수정해주기만 하면 됨