[알고리즘] 이진 탐색 (Binary Search)

1. 이진 탐색이란?

    탐색할 자료를 두 파트로 나누어 둘 중 찾으려는 자료가 있는 파트를 탐색 하는 것.
    탐색할 자료가 정렬이 된 경우에만 사용 가능하다.

 

 

 

2. 이진 탐색 살펴보기

    이진탐색은 친구들과 많이 했던 업다운 게임의 원리와 동일하다 보면 이해하기 쉽다. 
    한번 어떤 원리인지 살펴보자.

 

 

  1. 하단처럼 9개의 요소를 가진 정렬된 배열이 있다. 

 

  2. 해당 배열의 mid(중간 index의 값)을 추출한다.

  3. 찾으려는 자료값이 mid보다 큰지 작은지 비교한다. (같을 경우 mid의 index를 return한다)

 

  4. mid보다 큰 경우, 주황색 화살표 영역의 중간값과 다시 비교한다.

 

  5. mid보다 작은 경우, 파란색 화살표 영역의 중간값과 다시 비교한다.

  6. 2~5의 과정을 반복한다.

 

 

 

 

 

3. 이진 탐색 코드

func binarySearch(_ sortedArray: [Int], find: Int) -> Int {
     var low = 0
     var high = sortedArray.count-1
    
     while low <= high {
       let mid = (low + high) / 2   // 중간 index 설정
       
       if sortedArray[mid] == find {
          return mid
        } else if sortedArray[mid] < find {    // find가 중간 값보다 크다면 (주황 범위)
          low = middle + 1 // low의 범위 수정
        } else {      // find가 중간 값보다 작다면 (파란 범위)
          high = middle - 1    // high의 범위 수정
        }
     }
    return -1    // 빈 배열이거나 find에 해당되는 값이 배열에 없는 경우, -1을 리턴
}

 

사용 예시

 

 

 

3. 이진 탐색 시간복잡도

   이진 탐색은 n개의 요소를 가진 배열을 두 파트로 나누는 작업을 반복한다.

가장 시간이 오래 걸리는 경우, 배열의 길이가 1이 될 때까지 반복을 해야하므로 O(logN)의 시간복잡도를 가진다.