데일리썽

1. 이진 탐색 (Binary Search)

탐색할 자료를 둘로 나누어 해당 데이터가 있을만한 곳을 탐색하는 방법

2. 분할 정복 알고리즘과 이진 탐색

분할 정복 알고리즘 (Divide and Conquer)

• Divide : 문제를 하나 또는 둘 이상으로 나눈다.
• Conquer : 나눠진 문제가 충분히 작고, 해결이 가능하다면 해결하고, 그렇지 않으면 다시 나눈다.

이진 탐색

• Divide : 리스트를 두 개의 서브 리스트로 나눈다.
• Conquer :
  • 검색할 숫자 (search) > 중간값 이면 뒷 부분의 서브 리스트에서 검색할 숫자를 찾는다.
  • 검색할 숫자 (search) < 중간값 이면 앞 부분의 서브 리스트에서 검색할 숫자를 찾는다.

3. 구현

import lombok.extern.slf4j.Slf4j;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;

@Slf4j
public class BinarySearch {
    public static Boolean binarySearch(List<Integer> dataList, Integer search) {
        log.error("________________ = {}", dataList);

        if (dataList.size() == 1 && search == dataList.get(0)) {
            return true;
        }

        if (dataList.size() == 1 && search != dataList.get(0)) {
            return false;
        }

        if (dataList.size() == 0) {
            return false;
        }

        Integer medium = dataList.size() / 2;

        if (search == dataList.get(medium)) {
            return true;
        } else {
            if (search > dataList.get(medium)) {
                return binarySearch(dataList.subList(medium, dataList.size()), search);
            } else {
                return binarySearch(dataList.subList(0, medium), search);
            }
        }
    }

    public static void main(String[] args) throws Exception {
        Random rand = new Random();
        List<Integer> dataList = new ArrayList<>();
        for (int i = 0; i < 11; i++) {
            dataList.add(rand.nextInt(11));
        }

        Collections.sort(dataList);

        log.error("________________ = {}", binarySearch(dataList, 10));
    }
}

4. 분석

시간 복잡도는 O(logn)