이진검색(Binary Search)

개념 이해하기

만약 하나의 배열이 있다고 가정하였을경우
배열은 값을 검색하는것이 아닌 탐색하게 됩니다.

하지만 이렇게 탐색을 하게 될경우 배열의 길이가 길어지는 경우
오랜 시간이 걸릴뿐더러 최적화에 여러가지의 문제요소가 될수 있습니다.

그래서 Binary Search 를 이용한 선형검색을 하게 됩니다.

Binary Search 는 배열 요수중 중심을 찾습니다.
그후 질문을 통하여 중심을 기준으로 좌 우를 나뉘어 검색합니다.(1단계)
만약 중심을 기준으로 우측에서 값을 검색한다고 할경우 우측 요소들 중에서의 중심을 검색합니다(2단계)
그뒤 값을 추출하게 됩니다(3단계)

이렇게 되면 일반적인 선형탐색의 경우처럼 처음부터 끝까지 접근하는 방식이 아닌 훨씬 짧은 시간을 투자하여 값을 도출해낼수 있는 것입니다.

그럼 코드 구현으로 넘어가서 조금더 자세히 살펴보겠습니다.

let numbers = [1,4,10,14,18,22,25,31,105,135]

정수형 배열입니다.
여기서 먼저 살펴봐야할것은 정렬입니다.
이진 검색을 위해서 배열은 정렬이 되어 있어야 합니다.
그래야 값들을 검색하며 중심을 찾을수 있기 때문이죠

구현

// 배열의 왼쪽을 나타낼 변수(시작)
var lowBound = 0
// 배열의 오른쪽을 나타낼 변수(끝)
var upBound = numbers.count - 1
// 배열의 중심을 나타낼 변수(중간)
var middle = 0
// 검색의 여부를 나타낼 변수
var found = false
// 검색할 값
let valueToSearch = 31
// 검색
while(lowBound <= upBound) {
    // 배열의 중심 찾기
    middle = (lowBound + upBound) / 2
    // 중심에 찾을 값을 비교하여 검색하기.
    if (numbers[middle] == valueToSearch) {
        found = true
        break
        // 찾을 값이 중심의 값보다 클경우.
    }else if (numbers[middle] < valueToSearch ) {
        lowBound = middle + 1
    }else{
        // 찾을 값이 중심보다 작을 경우
        upBound = middle - 1
    }
}