[알고리즘 개념] 이진탐색

이진탐색은 원하는 수를 배열에서 탐색하고자 할 때, O(logN)으로 효율적인 탐색을 할 수 있게 해주는 알고리즘이다.

이진탐색은 배열의 처음과 끝을 직접 수정해나가며 원하는 값을 찾는 과정을 거친다.

 

이진탐색의 기본적인 과정

• 배열을 오름차순으로 정렬한다.
• 탐색할 배열의 처음과 끝을 의미하는 변수를 설정한다.(left, right)
• left와 right의 가운데 값(mid) 과 탐색하는 값을 비교한다.
• 크다면 -> left를 mid + 1로 수정한다.(mid보다 작은 쪽에는 원하는 값이 없는게 확실하니까)
• 작다면 -> right를 mid - 1로 수정한다.(mid보다 큰 쪽에는 원하는 값이 없는게 확실하니까)
• 만약 mid값과 탐색중인 값이 동일하면 index를 출력하고 종료한다(탐색 성공)
• 위 과정을 while문을 통해 반복하다가, left 가 right보다 커졌다면 탐색중인 값은 배열에 존재하지 않는다는 의미이므로 탐색 실패를 출력한다.

이진탐색을 활용한 문제의 코드이다.

import java.io.*;
import java.math.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        //int[] arr= new int[100000];

        int[] arr = new int[n];
         st = new StringTokenizer(br.readLine());

        for(int i = 0;i<n;i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
        
        //배열 정렬

        Arrays.sort(arr);

        for(int i = 0;i<m;i++){
            int a = Integer.parseInt(br.readLine());
            int left = 0; //left 초기값은 0
            int right = n-1;//right 초기값은 배열의 제일 끝
            int mid = 0;

            while(left <= right){
                mid = (left + right) /2; //left와 right의 가운데 값
                if(arr[mid] == a) { //탐색성공
                    sb.append((mid+1) + "\n");
                    //System.out.println(mid);
                    break;
                }
                else{
                    if(arr[mid] < a){ // 탐색하는 값이 mid값보다 크면
                        left = mid + 1;
                    }
                    else{//탐색하는 값이 mid값보다 작으면
                        right = mid -1;
                    }
                }
            }

            if(left > right){ //left가 right보다 크면 탐색 실패
                sb.append(-1 + "\n");
             }     
            }

        System.out.println(sb);
        


    }
}

 

출처 : 코드트리

https://www.codetree.ai/missions/8/problems/find-number-fast/description

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석