[Java] 순차 탐색, 이진 탐색의 개념과 예제

서론

---

이번 포스팅에선 순차 탐색과 이진 탐색의 개념에 대해 알아보고 간단히 Java로 구현해볼 예정입니다. 바로 시작하겠습니다.

 

---

 

순차 탐색(Sequential Search)이란?

---

탐색은 여러 데이터 중에서 원하는 데이터를 찾아내는 것을 의미한다. 순차 탐색은 데이터가 담겨있는 배열을 맨 앞부터 하나씩 비교하여 원하는 데이터를 찾는 방법을 말한다.

 

순차 탐색 구현

public class SequentialSearch {

    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>();

        for(int i=0; i<20; i++)
            list.add(i);

        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();

        System.out.println(searchFunc(list, num));
    }

    private static int searchFunc(ArrayList<Integer> list, int searchItem){

        for (int i = 0; i < list.size(); i++) {
            if(list.get(i) == searchItem)
                return i;
        }
        return -1;
    }
}

로직을 살펴보면 정말 단순한 구조이다. 입력값을 받아 0~20개가 담긴 list의 첫번째 원소부터 순서대로 탐색하여 원하는 값이 있는지 없는지 찾는 구조이며, return 값은 배열 중 찾는 값이 있다면 해당 인덱스 출력, 없다면 -1 출력 형식이다.

 

시간복잡도는 O(n)으로 표현할 수 있다.

 

이진 탐색(Binary Search)이란?

---

순차 탐색에 비해 난이도는 조곰 더 있지만 개념적으로 봤을 땐 그리 어렵지 않다. 정의 된 내용은 다음과 같다.

 

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

 

특징

• 분할 정복 알고리즘을 사용한다.
  • Divide: 리스트를 두 개의 서브 리스트로 나눈다.
  • Conquer
    • if(검색할 숫자 > 중간 값) 
      • [True] 뒷 부분의 서브 리스트에서 검색할 숫자를 찾는다.
    • if(검색할 숫자 < 중간 값) 
      • [True] 앞 부분의 서브 리스트에서 검색할 숫자를 찾는다.

 

이진 탐색 구현

public class BinarySearch {
    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>();

        for (int i = 0; i < 20; i++)
            list.add(i);

        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();

        System.out.println(searchFunc(list, num));
    }

    private static boolean searchFunc(ArrayList<Integer> list, int searchItem) {

        //사이즈가 1이고, 그 하나가 찾는 값과 같을 경우 -> True
        if (list.size() == 1 && searchItem == list.get(0)) {
            return true;
        }

        //사이즈가 1이고, 그 하나가 찾는 값과 다를 경우 -> False
        if (list.size() == 1 && searchItem != list.get(0)) {
            return false;
        }

        //리스트 사이즈가 0일 경우 -> False
        if (list.size() == 0) {
            return false;
        }

        int mediumSize = list.size() / 2;

        if (searchItem == list.get(mediumSize)) {
            return true;
        } else {
            if (searchItem < list.get(mediumSize)) {
                return searchFunc(new ArrayList<Integer>(list.subList(0, mediumSize)), searchItem);
            } else if (searchItem > list.get(mediumSize)) {
                return searchFunc(new ArrayList<Integer>(list.subList(mediumSize, list.size())), searchItem);
            }
        }

        return false;
    }
}

위에서 작성한 로직을 간단히 설명하자면, 이전 고급 정렬 알고리즘 포스팅에서 사용했던것과 같이 배열을 나눠서 재귀함수를 돌리는 구조이다. 찾는 값 < 중간 값이면, 좌측 배열에서 찾으며 조건이 false라면 우측 배열에서 찾게끔 작성하였다.

 

이렇게 이진 탐색을 사용할 경우 시간 복잡도는 O(logn)이 된다.