이진 탐색

서정한·2023년 6월 5일

알고리듬 이진탐색

알고리듬 공부

목록 보기

6/15

개요

탐색과 검색은 컴퓨터에서 매우 흔하고 중요하다.
데이터가 많아질 때 탐색속도가 현저히 줄어들 수 있다. 그럴때 사용하는것이 바로 이진탐색이다.

탐색 알고리듬

어떤 데이터 구조안에 저장되어있는 정보를 구해오는 알고리듬
매우 다양함
- 배열에서 제일 큰 값 찾기
- DB에서 레코드 하나 읽어오기
- 배낭(knapsack)문제
- 등...
대표적인 탐색 알고리듬
- 선형(linear) 알고리듬(O(N))
  - 맨 앞에서부터 순서대로 해당 값이 있는지를 찾고 해당값을 찾으면 종료.
- 해시맵을 이용한 탐색(O(1))
  - 입력값을 해시함수에 입력하여 key를 얻는다. 해당 key에 입력값(value)를 넣는다. 값을 찾는 것은 위의 역순으로 실행함.

선형탐색 vs 해시맵을 이용한 탐색

선형탐색
- 모든 데이터 사용가능
- O(N)
- N만큼의 용량이 필요
해시 맵 탐색
- 모든 데이터 사용가능
- O(1)
- N보다 큰 용량이 필요

데이터 성질과 알고리듬

특정 입력 데이터에서만 제대로 동작하는 것들이 필요함.
- 특화된 알고리듬.
- 효율성을 높이기 쉬움.
- 정수만 처리하는 알고리듬도 엄밀히 말하면 특화된 것.
- 필요에 따라 특화된 알고리듬을 사용하는것은 좋은 것이다.

Q. 다음과 같은 배열에서 10을 O(N)보다 빠르게 찾는 방법은?
데이터: [1,2,3,5,7,8,10,15,21,32,35,39,43,44,47,99]

데이터는 정렬되어있음.
- 어떤 위치의 값을 확인하면 다음 검색할 범위는 좌/우 중 하나.
- 오른쪽은 현재 값보다 큰 것을 저장.
- 왼쪽은 현재 값보다 작은 값들을 저장.

이진탐색 알고리듬

정렬된 배열에서 어떤 값의 위치를 찾는 알고리듬
한단계 진행할 때마다 탐색범위가 절반으로 줄어들기때문에 이진(binary)라는 이름이 탄생하였음.
분할정복(divide-and-conquer)알고리듬 중 하나
- 분할정복이라고 말하려면 원칙상 모든 문제영역을 방문해야하지만 이진탐색 알고리듬은 그렇지 않음.
- decrease-and-conquer라고 부르자는 소수설도 있다고 함.
재귀함수로 쉽게 작성가능

fun binarySearchRecursive(arr: Array<Int>, target: Int) : Int {
    return binarySearchRecursiveHelper(arr, target, 0, arr.size - 1)
}

fun binarySearchRecursiveHelper(arr:Array<Int>, target:Int, low: Int, high: Int) :Int {
    if(low > high) return -1

    val mid = (low + high) / 2
    val midValue = arr[mid]

    return when {
        target == midValue -> mid
        target < midValue -> binarySearchRecursiveHelper(arr, target, low, mid - 1)
        else -> binarySearchRecursiveHelper(arr, target, mid + 1, high)
    }
}

이진탐색 알고리듬 설명
1. L = 0, R = idx -1
2. if(L > R) 알고리듬 종료(찾기 실패)
3. m = (L + R) / 2
4. if(nums[m] < value) L = m + 1 후 2번으로 돌아감
5. if(nums[m] > value) R = m - 1 후 2번으로 돌아감
6. if(nums[m] == value) return m 후 종료

정렬된 데이터와 알고리듬

정렬된 데이터에 사용할 수 있는 효율적인 알고리듬이 많다!
- 어떤 값의 위치 찾기: O(log n)
- 최소값/최대값 찾기: O(1)
정렬되지 않은 배열은?
- 일단 정렬!(정렬 알고리듬을 사용)
- 만약, 배열에 새 요소를 추가하면 다시 정렬해야 함.. ㅠ
  - 정렬 알고리듬이 이진 탐색보다 시간복잡도가 높다.

정렬 후 이진탐색 vs 선형탐색

배열이 안바뀌는 경우
- 탐색할 일이 많은 경우
  - 정렬 한번 후, 이진 탐색 여러번이 훨씬 효율적!
  - O(정렬) + O(log n)*X
- 탐색을 한번만 할 경우 => 선형탐색( O(n) )
배열이 바뀌는 경우
- 요소를 삽입하는 경우만 문제(지우는 경우는 순서가 바뀌지 않음)
- 보통 선형 탐색을 사용
- 이진탐색을 사용하려면?
  - 탐색 전 배열을 정렬해야 함.
    - 배열이 바뀔 때마다 곧바로
    - 배열이 바뀐적이 있다면 탐색 직전에
  - 선형탐색보다 느릴 수 있다.
    - 탐색과 배열 변경 빈도에 따라(당연..!)
    - 탐색 빈도가 높을수록 유리(탐색이 많다면 정렬 후 탐색이 보통 유리하기때문)