9.md

이진탐색을 코드로 구현하고 설명해주세요.

• 이진탐색이란?

  • 이진 탐색은 배열 내부의 데이터가 정렬되어 있을 때만 가능한 알고리즘으로, 탐색 범위를 반 씩 좁혀가면서 데이터를 탐색하는 알고리즘이다.
  • 최악의 경우 O(logN) 의 시간 복잡도를 가진다.
  • 리스트의 길이가 길수록 효율적인 알고리즘이다.

• 예시

90 값이 존재하는 인덱스를 찾아보자

• 위와 같이 배열이 존재한다면 먼저 시작 인덱스와 끝 인덱스를 지정하여 중간 인덱스를 구한다. ( 여기서 반드시 배열은 정렬된 상태여야한다. )

• 중간 인덱스에 해당하는 값 50 은 target인 90 보다 작기 때문에 start 값을 mid + 1 로 변경하여 검사 영역을 오른쪽 영역으로 변경한다.

• 위와 같이 오른쪽 영역으로 좁힌 이후에도 mid의 값이 90 보다 작으므로 영역을 또 한번 오른쪽 영역으로 변경한다.

• 영역을 좁힌 이후에 mid 값인 90 이 우리가 찾으려는 target 이므로 해당 값을 리턴한다.

---

• 구현

    fun binarySearch(arr: IntArray, target: Int): Int {
        var start = 0
        var end = arr.lastIndex

        while (start <= end) { // 시작 인덱스가 끝 인덱스보다 크거나 같을 때 계속 반복
            val mid = (end + start) / 2 // 중간 인덱스을 찾아준다.
            when {
                arr[mid] == target -> return mid // 중간 인덱스의 값이 target 과 같으면 끝낸다.
                arr[mid] > target -> end = mid - 1 // 중간 인덱스의 값이 target 값보다 크면 왼쪽 영역 선택
                else -> start = mid + 1 // 중간 인덱스의 값이 target 값보다 작으면 오른쪽 영역 선택
            }
        }
        return -1 // arr 내에서 target 값을 찾을 수 없는 경우 -1 반환
    }

시간복잡도

• 이진 탐색의 시간복잡도는 O(logN)입니다.
• 입력된 데이터가 N이라 할 때 이를 반으로 나눠가면서 탐색을 하게 됩니다. 최악의 경우에는 데이터 하나만 남을 때까지 반으로 나누게 될 것입니다. 이를 식으로 적어보면 다음과 같습니다.

- 따라서 연산 횟수는 대략적으로 logN번 시행되고 이진 탐색은 O(logN)의 시간을 가진다고 말할 수 있습니다.

---

참고

• 이것이 코딩 테스트다 ( 나동빈 저 )
• https://blog.penjee.com/binary-vs-linear-search-animated-gifs/