[알고리즘] 이진검색 패턴

알고리즘 / 이진검색

이진검색을 구현하는 것은 대게 어렵지 않으나 구현할 때마다 헷갈린다.
아래와 같이 구현하면 대부분의 경우를 만족시킬 수 있다.

패턴


    arr := []int{1, 1, 2, 2, 2, 4, 4, 5, 5, 5}
    l := 0
    r := len(arr) // 배열 끝 index보다 1이 커야 한다
    t := 3 // target

    for l < r { // 혹은 l != r
        // floor를 적용
        // (l + r)/2는 overflow가 발생할 수 있음
        m := l + (r-l)/2 
        if arr[m] < t { // 왼쪽 영역 + 가운데를 버리는 조건
            // floor적용에 따른 무한루프 방지를 위해 left에 1을 더함
            l = m + 1
        } else { // 오른쪽 영역을 버리는 조건
            r = m
        }
    }
    
    // t의 존재 유무가 필요한 경우
    if arr[l] == t {
        fmt.Println("found")
    } else {
        fmt.Println("not found")
    }

    // 경계를 확인하고 싶은 경우
    fmt.Println("idx:", l)

위 코드는 아래의 경우를 모두 만족한다.

  1. 정확한 t를 찾는 경우
  2. 중복이 있는 경우 left-most를 찾는 경우

참고로 right-most를 구하기 위해서는 아래처럼만 수정하면 된다.

arr[m] < t  =>  arr[m] <= t

응용

이진탐색은 탐색을 지속하면서 왼쪽 혹은 오른쪽을 계속 버리는 것과 같다.

위 코드에서 첫 if 절 조건이

  • 참이면 왼쪽 영역과 가운데를 버린다.
  • 거짓이면 오른쪽 영역을 버린다.

다른 케이스에서도 위의 패턴을 유지한 채 if 조건만 수정하면 된다.

l = m + 1 과 r = m 코드는 무한루프를 막기 위해 필요한데 이는 m을 구하는 코드가 floor를 적용했기 때문이다. 만약 ceil을 적용했다면 l = m, r = m - 1 형태로 바뀌어야 한다.

참고

 
comments powered by Disqus