이진 탐색

순차 탐색

순차 탐색은 우리가 가장 처음 어떤 프로그래밍 언어를 배우든간에 반복문을 배울 때 자주쓰던 익숙한 탐색 알고리즘이다. 말 그대로 리스트(배열) 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 순차적으로 탐색하는 알고리즘이다.

코드 예시를 하나 들어보면 다음과 같다.

import java.util.Scanner;

public class MySourceCode {

    public static int sequentialSearch(String[] arr, String target){

        for(int i = 0; i < arr.length; i++){
            //찾는 문자열이 있다면 인덱스 출력
            if(arr[i].equals(target)){
                return i;
            }
        }
        //찾는 문자열이 없다면 -1 출력
        return -1;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //원소의 갯수 입력
        int n = sc.nextInt();
        //찾을 문자열 입력
        String target = sc.next();
        sc.nextLine();  //버퍼 비우기
        //문자열을 담을 공간
        String[] arr = sc.nextLine().split(" ");

        int result = sequentialSearch(arr, target);
        
        System.out.println("result = " + result);
    }
}

이진 탐색

이진 탐색은 리스트(배열)의 내부의 데이터가 정렬되어 있어야 사용할 수 있다. 데이터가 무작위이면 사용 불가능하지만 데이터가 정렬되어있다면 매우 빠르게 동작하는 탐색 알고리즘이다. 이진 탐색은 위치를 나타내는 변수 3개를 사용하는데 탐색하고자 하는 범위의 시작점, 끝점, 중간점을 이용한다. 이해를 위해 아래 예시를 적어두었다.

import java.util.*;

public class MySourceCode {

    public static int binarySearch(int[] arr, int target, int start, int end){
        //찾는 원소가 없을 경우 종료
        if(start > end) return -1;
        //중간 인덱스
        int mid = (end - 1) / 2;
        //이진 탐색 시작
        if(target == arr[mid]) return mid;
        else if(target > arr[mid]) return binarySearch(arr, target, mid + 1, end);
        else return binarySearch(arr, target, start, mid - 1);

    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        //원소의 갯수 입력받기
        int n = sc.nextInt();

        int[] arr = new int[n];

        //찾을 숫자 입력받기
        int target = sc.nextInt();
        //원소 입력받기
        for(int i = 0; i < n; i++){
             arr[i] = sc.nextInt();
        }
        //배열 정렬
        Arrays.sort(arr);

        int result = binarySearch(arr, target, 0, n-1);

        System.out.println("result = " + result);

    }

}