Binary Search - 이진 검색

배열에서 찾으려는 값이 있는지 이진 검색을 합니다.
배열의 범위를 2분할 하면서 찾는 방법입니다.

https://en.wikipedia.org/wiki/Binary_search_algorithm

Binary search algorithm - Wikipedia

Go로 구현한 코드입니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
package main
import "fmt"
func main() {
    searchValue := 4
    arr := [10]int{1, 5, 100, 0, -100, 15, 4, 102, 30, 1000}
    fmt.Println(arr)
    // 검색하려면 먼저 정렬이 되어있어야 합니다. 버블정렬로 배열을 정렬합니다.
    for i := 0; i < len(arr); i++ {
        for j := 0; j < len(arr)-1; j++ {
            if arr[j] > arr[j+1] {
                arr[j], arr[j+1] = arr[j+1], arr[j]
            }
        }
    }
    fmt.Println(arr)
    // 찾으려는 범위를 left와 right로 지정합니다.
    // 초기값으로 배열의 전체(처음과 끝 자리)를 지정합니다.
    left := 0
    right := len(arr) - 1
    // 배열의 마지막 자리(right)가 left(0)보다 작다면 빈 배열입니다.
    if right < left {
        fmt.Println("Not found")
        return
    }
    // 찾으려는 범위(left, right)가 같거나 클때까지 loop를 진행합니다.
    for left <= right {
        // 찾으려는 범위에서 중간 값을 찾습니다.
        mid := (left + right) / 2
        // 중간 자리의 값이 찾으려는 값과 같다면 해당 자릿수를 출력합니다.
        if arr[mid] == searchValue {
            fmt.Println("Found at position: ", mid)
            return
            // 만약 찾으려는 값이 중간값보다 크다면 left를 중간값 다음 자리로 지정합니다.
        } else if arr[mid] < searchValue {
            left = mid + 1
            // 만약 찾으려는 값이 중간값보다 작다면 right를 중간값 이전 자리로 지정합니다.
        } else {
            right = mid - 1
        }
    }
    fmt.Println("Not found")
}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

찾으려는 범위를 지정하고 범위의 중간값을 비교합니다.
만약 중간값이 찾으려는 값보다 작다면 오른쪽에서 검색하고 크다면 왼쪽에서 검색합니다.

이렇게 범위를 좁혀가며 찾습니다.