이진탐색

영어사전에서 goose 를 찾고싶을 때 사전은 abcd.. 순으로 정렬되어 있다는 것을 알기 때문에

굳이 a 단어들을 모여놓은 곳에서 찾지 않고 g 단어를 모아놓은 곳에서 부터 찾을 것이다.

찾고자 하는 범위에서 중간값이 찾고자 하는 것과 일치하는 지 확인

일치하면 중간값의 위치를 리턴

중간값이 찾고자 하는 값보다 크면 최대값을 중간값위치 -1 로 범위를 재조정

중간값이 찾고자 하는 값보다 작으면 최소값을 중간값위치 +1 로 범위를 재조정

중간값을 구할 수 없을 때까지 반복

범위가 얼마나 많던 간에 O(log n ) 에 끝난다. 탐색을 하면 할 수록 탐색의 범위가 줄어든다.

binary search 함수는 정렬된 배열하나와 어떤 아이템을 받는다. 만약 아이템이 배열안에 있으면 배열에서의 아이템 위치를 반환한다.

import math

array = list(range(1, 101))

item = 75

def binary_search(item: int) -> int or None:

    min_index = 0
    max_index = len(array)-1

    while min_index <= max_index:

        middle_index = math.floor((min_index+max_index) / 2)

        if(array[middle_index] == item):
            return middle_index

        if(array[middle_index] > item):
            max_index = middle_index-1

        if(array[middle_index] < item):
            min_index = middle_index+1

    return None

print(binary_search(item))

import java.lang.Math;

public class BinarySearch {

    private static int binarySearch(int item, int[] array) {

        int minIndex = 0;

        int maxIndex = array.length - 1;

        while (minIndex <= maxIndex) {

            int middleIndex = (int) Math.floor((minIndex + maxIndex) / 2);

            if (array[middleIndex] == item) {
                return middleIndex;
            }

            if (array[middleIndex] > item) {
                maxIndex = middleIndex - 1;
            }

            if (array[middleIndex] < item) {
                minIndex = middleIndex + 1;
            }

        }
        return -1;
    }

    public static void main(String[] args) {

        int[] array = new int[100];

        for (int i = 0; i < array.length; i++) {
            array[i] = i + 1;
        }

        int item = 65;
        System.out.println(binarySearch(item, array));

    }
}