[알고리즘, 자료구조] 이진 검색

이진 검색이란?
데이터가 오름차순 또는 내림차순으로 정렬된 배열에서 검색하는 알고리즘

어떤 원리인가?
1. 배열의 중앙의 요소(pc)를 기준으로 검색값과 비교 
2. 중앙값이 key보다 크면 ? 중앙값~오른쪽 인덱스(pr) 사이의 중앙값을 기준으로 다시 검색값과 비교
3. 중앙값이 key보다 작으면 ? 왼쪽 인덱시(pl) ~ 중앙값 사이의 중앙값을 기준으로 다시 검색값과 비교


*비교 횟수의 평균값은 log n으로 검색이 훨씬 빠름

 

작동 원리: 

 

1. 요솟값을 입력받아 빈 배열을 만든다. 

//요솟값을 입력받는다.
Scanner sc = new Scanner(System.in);
System.out.print("요솟수(1에서 999까지 입력가능합니다) : ");
int n = sc.nextInt();

//요솟수만큼의 길이를 가진 배열 형성
int[] x = new int[n];

 

2. 빈 배열에 값을 넣기

    //x[0]에 값을 넣기
    //남은 배열에 값을 다 넣을 수 없을 경우 다시 값 재부여
    Random rand = new Random();
    for(; true ;){
      x[0] = rand.nextInt(999) + 2 - n;  //rand는 0에서 999사이의 값 -> 1에서 1000사이의 값
      if (!(x[0] <= 0)) break;
    }
    System.out.printf("x[0] = %d\n", x[0]);

    //각 배열에 값 넣기 (0을 넣었으니 1부터)
    //다만, 이전값보다 클 것
    for (int i = 1; i < x.length; i++) {
      int randInt = rand.nextInt(999) + 1; //rand는 0에서 999사이의 값 -> 1에서 1000사이의 값
      for (; true; ) {
        if (randInt > x[i - 1] && randInt <= 1000 - (n - i)){// 값이 이전값보다 작거나 남은 배열에 값을 다 넣을 수 없는 경우
          x[i] = randInt;
          System.out.printf("x[%d] = %d\n", i, x[i]);
          break;
        } else randInt = rand.nextInt(999) + 1; //다시 랜덤값 부여
      }
    }

 

이 알고리즘을 짜는데 상당히 고생하였다. 이진 검색은 정렬이 되어야 한다. 그런데 필자는 랜덤값으로 이를 실행하려고 하다보니 꽤나 어려움이 있었다. 

 

첫번째 고민은 '지금값과 이전값과 비교하는 반복문'을 사용하면 이전값이 없는 x[0]이 실행될 수 없다는 문제에 직면하였다. 이를 해결하기 위해 x[0]은 for문 이전에 먼저 정의하였다. x[0]이 지정되었으니 for문은 i=1부터 시작한다. for문을 만들기에는 순조로웠다. 그런데 여러번 반복을 하다보니 큰 문제가 있음을 발견하였다. 

 

여기서 두번째 고민이 발생한다. 현재 random값의 범위는 1에서 999까지 지정되어 있다. 그런데 x[1] = 999가 된다면 x[2]는 999외에는 값이 지정될 수 없다. 그러면 중복값을 인정해주어야할까? 그럴 수 없다. 왜냐하면 이진 검색은 모든 데이터를 확인하지 않기 때문에 중복된 값이 들어가면 나중에 위치를 반환할 때 정확도가 현저히 떨어질 수 있다. 

 

그래서 중복을 제거하기 위해 꽤나 고심하였다. 결국, x[i]는 남아있는 배열을 고려하여 값이 배정되도록 하였다. 이렇게 코드를 짜보니 x[0]값도 남아있는 배열을 고려하여 값이 배정되도록 재조정하였다. 

 

3. 검색값 입력

//검색값 입력(n)
System.out.print("검색할 값: ");
int key = sc.nextInt();

//검색 실시
int idx = binSearch(x, n, key);

 

직관적이다. 배열, 요솟값, 검색값을 매개변수로 해서 검색을 실시하는 binSearch 메서드가 실행된다. 

 

4. 검색 시작(이진 검색)

static int binSearch(int[] x, int n, int key){
  int pl = 0; //검색 시작
  int pr = n-1; //검색 끝
  for(; true ;){
    int pc = (pl+pr)/2; //검색 시작과 끝의
    if(x[pc] == key) return pc;
     else if(pl == pr) return -1;
     else if(x[pc] > key) pr = pc-1; // 검색 끝 변경
     else if(x[pc] < key) pl = pc+1; //검색 시작 변경
  }
}

생각보다 코드를 구상하기는 어렵지 않은데 for문을 빠져나가지 못하는 문제가 생겨서 시간이 조금 걸렸다. 알고보니 else if(pl==pr)을 아래에 배치하여 생긴 문제였다. pl==pr인 상황일 때 pr = pc-1 혹은 pl = pc+1이 먼저 실행되어서 pl==pr이 계속 실행되지 않았다. 배치를 다시하니깐 정상 작동하였다. 

 

5. 검색 결과 출력

//검색 결과 출력
if (idx == -1) System.out.println("검색값이 없습니다.");
  else System.out.printf("그 값은 x[%d]의 위치에 있습니다.", idx);

 

p.s.

수정) 24.06.24

중복을 제거하지 않고도 검색하는 방법이 있어서 내용을 추가하였다. 

무한 반복문에 다음 함수를 집어넣으면 된다. 

if (a[pc] == key) {
  for ( ; pc > pl; pc--) // key와 같은 맨앞의 요소를 검색합니다
   if (a[pc - 1] < key)
    break;
  return pc;       // 검색 성공

a[pc]가 key값과 동일하더라도 pc의 값을 계속 떨어뜨리면서 반복을 확인할 수 있다.