Algorithm 이분검색, 이진검색, 이분탐색, 이진탐색

2분 검색? 2분만에 검색하기!!!!???? 하하하하하하

아니죠

두 이, 나눌 분

두개로 나눠서 검색한다~ 맞습니다 하하하하

 

이분검색을 알았을 때 정말 깜~짝 놀랐다 

이런 상큼한 방법이 있다니 !

 

오늘은 ~ 상큼빵큼한 이분검색에 대해 기록해보자!!! 아하하하

 

 설명 

이분검색은 정렬된 데이터를 반씩 쪼개가며 원하는 데이터를 찾다. 

 

[ 1, 2, 3, 4, 5, 6, 7, ]

1부터 7까지의 수중에 5의 위치를 찾는경우 for문을 돌려 1부터 7까지 하나하나 찾기 시작하면, 시간복잡도는 O(n)이다. 전체를 다 뒤져야하기 때문이다.

 

이분검색은 다르다. 전체를 하나하나 검색하지 않고, 최소한의 수를 찾아가며 검색하기 때문이다.

 

1)  1과 7의 중간 숫자인 4를 찾는다.

2)  중간숫자인 4와 찾는 숫자 5의 크기를 비교한다.

   -  if (중간숫자 == 찾는숫자) { answer=중간숫자의 인덱스+1; break; } 

                                // 정답발견!!!

   -  if (중간숫자 > 찾는숫자) { rt=중간숫자 인덱스-1; } 

                               // rt를 중간숫자보다 1만큼 작게 변경한다.

                                why? 찾는숫자가 중간숫자보다 보다 더 작기 때문에 범위를 0~3으로 줄여서 재검색할거다.

   -  if (중간숫자 < 찾는숫자) { lt=중간숫자 인덱스+1; } 

                               //  lt를 중간숫자보다 1만큼 크게 변경한다.

                                why? 찾는숫자가 중간숫자보다 보다 더 크기 때문에 범위를 5~7으로 줄여서 재검색할거다.

3)  반복/재귀 

 

 

이게 이분검색의 방식이다. 검색해야하는 범위를 반으로 쪼갠다음, 중간데이터와 찾아야하는 데이터와 크기비교를 하는것. 정답을 찾을 때까지 반으로 쪼개서 데이터 비교하기를 반복한다.

 

이분검색을 사용하면 속도를 기가막히게 줄여준다. 시간복잡도는 O(n) → O(log n) 로 줄어든다.

단, 이분검색을 사용하려면 "정렬"이 먼저 이뤄져야한다. 

 

 

아래의 문제와 코드를 확인하며 이분검색방법을 익히자~~

 

문제 :

임의의 N개의 숫자가 입력으로 주어집니다. N개의 수를 오름차순으로 정렬한 다음 N개의 수 중 한 개의 수인 M이 주어지면 이분검색으로 M이 정렬된 상태에서 몇 번째에 있는지 구하는 프로그램을 작성하세요. 단 중복값은 존재하지 않습니다.

입력 : 
첫 줄에 한 줄에 자연수 N(3<=N<=1,000,000)과 M이 주어집니다.두 번째 줄에 N개의 수가 공백을 사이에 두고 주어집니다.

 

예시 입력 : 

8 32

23 87 65 12 57 32 99 81

 

정답 :

3

import java.util.*;

class Main{
	public static void main(String args[]){
    	Scanner in=new Scanner(System.in);
      	int n=in.nextInt(), m=in.nextInt();
      	int[] arr=new int[n];
      	for(int i=0;i<n;i++) arr[i]=in.nextInt();
      	Arrays.sort(arr);  //오름차순 정렬
      
      	int lt=0, rt=n-1, answer=0;
       
      	while(lt<=rt){ //lt와 rt가 같거나, lt가 rt보다 작아야만 while이 돌아간다. lt와 rt가 동일할 때, 정답이된다.
        	int mid=(lt+rt)/2;  //중간값 구하기

			if(arr[mid]==m){
          	    answer=mid+1; break;
                //정답발견 !
            }else if(arr[mid]>m){
          	    rt=mid-1;
                //검색할 데이터를 반으로 줄여줌
            }else{
          	    lt=mid+1;
                //검색할 데이터를 반으로 줄여줌
            }
        }
      System.out.print(answer);
    }
}

 

 

문제 :

임의의 N개의 숫자가 입력으로 주어집니다. N개의 수를 오름차순으로 정렬한 다음 N개의 수 중 한 개의 수인 M이 주어지면 이분검색으로 M이 정렬된 상태에서 몇 번째에 있는지 구하는 프로그램을 작성하세요. 단 중복값은 존재하지 않습니다.

입력 : 
첫 줄에 한 줄에 자연수 N(3<=N<=1,000,000)과 M이 주어집니다.두 번째 줄에 N개의 수가 공백을 사이에 두고 주어집니다.

 

 

예시 입력 : 

8 32

23 87 65 12 57 32 99 81

 

정답 :

3