Binary Search - 이진 검색

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

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

Binary search algorithm - Wikipedia

Go로 구현한 코드입니다.

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")
}

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

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