[알고리즘, 자료구조] Arrays.binarySearch에 의한 이진검색

 

알고리즘, 자료구조	링크
선형검색	https://ycraah.tistory.com/18
보초법	https://ycraah.tistory.com/24
이진검색	https://ycraah.tistory.com/27

 

binarySearch란?
자바가 제공하는 배열에서 이진 검색을 하는 표준 라이브러리

어떻게 사용하는가?
static int binarySearch(배열, 검색값)
-배열과 검색값은 자료형을 명시해야함

결과는 어떻게 나오는가?
1. key값과 일치하면 인덱스 반환
2. key값과 일치하지 않으면 있어야 할 위치(삽입 포인트)를 추정할 수 있는 값을 음수로 반환

장점은?
1. 이진 검색 메서드를 직접 작성할 필요가 없음 
2. 배열 요소의 자료형과 관계없이 검색 가능

문제점은?
이진검색과 마찬가지로 맨 앞에 있는 요소의 인덱스를 반환한다는 보장이 없음

 

public class BinSearch {
  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; //검색 시작 변경
    }
  }

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

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

    //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; //다시 랜덤값 부여
      }
    }

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

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

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

이진검색에서 사용했던 코드이다.  

입력값은 랜덤으로 부여받고, 중복은 허락하지 않아서 위에서 말한 문제점은 발생하지 않는다. 

이를 Arrays.binarySearch를 사용하면 다음과 같이 바꿀 수 있다. 

 

위 코드에서 무한반복문이 제거되기 때문에 조금 더 깔끔해진다. 

public class BinarySearchTester {
  public static void main(String[] args) {
    //요솟값을 입력받는다.
    Scanner sc = new Scanner(System.in);
    System.out.print("요솟수(1에서 999까지 입력가능합니다) : ");
    int n = sc.nextInt();

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

    //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; //다시 랜덤값 부여
      }
    }

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

    //검색 실시
    int idx = Arrays.binarySearch(x,key);

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

 

다만, 이진 검색을 직접 작성한다면 맨 앞의 요소를 찾을 수 있도록 코드를 추가할 수 있다.