Go. BinarySearch

정렬된 배열에서 찾고자하는 값이 있는지 확인하는 검색 방법입니다.

물론 순차로 앞에서 부터 찾아도 되고 반으로 나누어서 찾아봐도 되고 방법은 여러가지 입니다.

 

이진 검색이라고 한국어로 표현하는데요.

이것을 이용하여 중간의 값을 구하고 이것보다 원하는 값이 중간 값보다 큰지 작은지를 비교해서 구현이 가능합니다.

 

개인적으로 요즘 find 자체의 구현들이 굉장히 빠른 알고리즘으로 되어 있어서 이것말고 find를 쓰는게 나을겁니다.

실제 현업에서 이런거 만들고 있을 시간도 없고요.

 

테스트 케이스중에 만약 중복되는 숫자가 들어가 있을 경우에 제일 앞에 숫자만 리턴하는 조건을 더 추가하였는데요.

binarySearch function 의 if문에 그 부분이 들어가 있습니다.

한단계 앞에 숫자가 같은 숫자면 한번 더 조회를 하게 하는거죠.

package main

import (
    "fmt"
)

func main() {
    result1 := findIndex([]int{1, 2, 9, 78, 124}, 9)
    assertEqual(result1, 2)
    
    result2 := findIndex([]int{1, 2, 9, 78, 124, 129}, 9)
    assertEqual(result2, 2)
    
    result3 := findIndex([]int{1, 2, 9, 78, 124}, 100)
    assertEqual(result3, -1)
    
    result4 := findIndex([]int{1, 2, 9, 78, 124, 129}, 100)
    assertEqual(result4, -1)
    
    result5 := findIndex([]int{1, 2, 9, 9, 78, 124}, 9)
    assertEqual(result5, 2)
    
    result6 := findIndex([]int{1, 2, 9, 9, 78, 124, 129}, 9)
    assertEqual(result6, 2)
}

func findIndex(array []int, target int) int {
    return binarySearch(array, 0, len(array) - 1, target)
}

func binarySearch(array []int, start int, end int, target int) int {
    center := (start + end) / 2
    
    if array[center] == target {
        before := center - 1
        if before >= 0 && array[before] == target {
            return binarySearch(array, start, before, target)
        } else {
            return center
        }
    } else if start >= end {
        return -1
    } else if target > array[center] {
        return binarySearch(array, center + 1, end, target)
    } else if target < array[center] {
        return binarySearch(array, start, end - 1, target)
    }
    
    return -1
}

func assertEqual(output int , expected int) {
    if output == expected {
        fmt.Println("sueecess. value is", output)
    } else {
        fmt.Println("fail. output is", output, ", expected is", expected)
    }
}