이진검색 알고리즘 (구현 메소드 사용, Arrays.binarySearch 라이브러리 사용)

이진검색법

이진검색 알고리즘을 적용하는 전제조건은 데이터가 키 값으로 이미 정렬 되어 있다는 것이다.

이진검색은 요소가 오름차순 또는 내림차순으로 정렬된 배열에서 검색하는 알고리즘이다.

1. 이진검색 알고리즘 ( 메소드 구현 방법, Arrays.binarySearch 표준라이브러리 사용방법 ) 

package myTest1;
 
import java.util.Arrays;
import java.util.Scanner;
 
public class BinarySearch {
 
    // 이진 검색
    static int binarySearch(int[] array, int arrayLength, int searchValue){
        int first = 0;                            // 검색 범위의 첫 인덱스
        int last = arrayLength-1;        // 검색 범위의 끝 인덱스
        
        do{
            int center = (first +  last) /2 ; // 중앙 요소의 인덱스
            if(array[center] == searchValue) 
                return center;    // 검색 성공
            else if(array[center] < searchValue) 
                first = center+1;    // 검색 범위를 뒤쪽 절반으로 좁힘
            else 
                 last = center -1;    // 검색 범위를 앞쪽 절반으로 좁힘
        }while(first <=  last);
        return -1;        // 검색 실패
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("배열 길이 : ");
        int arrayLength = scanner.nextInt();
        int[] array = new int[arrayLength];    // 요솟수가 num인 배열
        System.out.println("오름차순으로 입력");
        
        System.out.print("array[0] : ");
        array[0] = scanner.nextInt();
        
        for(int i=1; i<arrayLength; i++){
            do{
                System.out.print("array[" + i + "] : ");
                array[i] = scanner.nextInt();
            }while(array[i] < array[i-1]);        // 바로 앞의 요소보다 작으면 다시 입력
        }
        
        System.out.println("검색할 값");    // 키 값을 입력
        int searchValue = scanner.nextInt();
        // 구현한 binarySearch 메소드 사용
        int idx = binarySearch(array, arrayLength, searchValue);        
        // Arrays.binarySearch 이진검색 표준라이브러리 사용
        int idx2 = Arrays.binarySearch(array, searchValue);
        
        if(idx == -1){
            System.out.println("구현한 이진검색 메소드 결과 그 값의 요소가 없습니다.");
        }else{
            System.out.println("구현한 이진검색 메소드 결과 "+searchValue+"은(는) array["+idx+"]에 있습니다.");
        }
        
        if(idx2 == -1){
            System.out.println("구현한 이진검색 메소드 결과 그 값의 요소가 없습니다.");
        }else{
            System.out.println("Arrays.binarySearch 표준 라이브러리 사용결과 "+searchValue+"은(는) array["+idx2+"]에 있습니다.");
        }
        
        
    }
}

결과

2.  Arrays.binarySearch 표준라이브러리 사용해 String 검색하기

package myTest1;
 
import java.util.Arrays;
import java.util.Scanner;
 
public class StringBinarySearch {
 
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String[] x = {
            "apple", "banana", "cocoa", "duck", "element", "final",
            "grape", "honey", "ice", "jerry", "king", "leaf", "monkey"
        };
        System.out.println("키워드를 입력: ");
        String searchKey = scanner.next();
        
        int idx = Arrays.binarySearch(x, searchKey);    // 배열 x에서 값이 searchKey 요소 검색
        
        if( idx < 0){
            System.out.println("해당 키워드가 없습니다.");
        }else{
            System.out.println("해당 키워드는 x[" + idx + "]에 있습니다.");
        }
    }
}

결과

3. 제네릭과 생성자를 사용하여  Arrays.binarySearch(T[] a, T key, Comparator<? super T>c) 표준라이브러리 메소드 사용하기

 The array must be sorted into ascending orderaccording to the specified comparator

이진검색 알고리즘을 사용할 경우 정렬되어야 한다.

package myTest1;
 
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
 
public class ConstructorBinarySearchLibrary {
    // 신체검사 데이터 정의
    static class PhyscData{
        private String name;    // 이름
        private int height;        // 키
        private double vision;    // 시력
        
        // 생성자
        public PhyscData(String name, int height, double vision){
            this.name = name; 
            this.height = height; 
            this.vision = vision;
        }
        
        // 문자열을 반환하는 메서드
        public String toString(){
            return name + " " + height + " " + vision;
        }
        
        public static final Comparator<PhyscData> HEIGHT_ORDER = new HeightOrderComparator();
        public static final Comparator<PhyscData> VISION_ORDER = new VisionOrderComparator();
        
        private static class HeightOrderComparator implements Comparator<PhyscData>{
            public int compare(PhyscData d1, PhyscData d2){
                return (d1.height > d2.height) ? 1:
                            (d1.height < d2.height) ? -1 : 0;
            }
        }
 
        private static class VisionOrderComparator implements Comparator<PhyscData>{
            public int compare(PhyscData d1, PhyscData d2){
                return (d1.vision < d2.vision) ? 1:
                    (d1.vision > d2.vision) ? -1 : 0;
            }
        }
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 키 오름차순, 시력 내림차순 정렬
        PhyscData[] arrays = {
                new PhyscData("윤아", 160, 1.5),
                new PhyscData("태연", 161, 1.4),
                new PhyscData("티파니", 162, 1.3),
                new PhyscData("제시카", 163, 1.2),
                new PhyscData("유리", 164, 1.1),
                new PhyscData("서현", 165, 1.0),
                new PhyscData("써니", 166, 0.9),
        };
        
        System.out.print("몇 cm인 사람을 찾고 있나요? : ");
        int height = scanner.nextInt();
        int idx = Arrays.binarySearch(arrays, new PhyscData("", height, 0.0), PhyscData.HEIGHT_ORDER);
        if(idx < 0){
            System.out.println("요소가 없습니다.");
        }else{
            System.out.println("arrays[" + idx + "]에 있습니다.");
            System.out.println("찾은 데이터 : " + arrays[idx]);
        }
        
        System.out.println("시력이 몇인 사람을 찾나요?");
        double visionValue = scanner.nextDouble();
        int idx2 = Arrays.binarySearch(arrays, new PhyscData("", 0, visionValue), PhyscData.VISION_ORDER);
        if(idx2 < 0){
            System.out.println("요소가 없습니다.");
        }else{
            System.out.println("arrays[" + idx2 + "]에 있습니다.");
            System.out.println("찾은 데이터 : " + arrays[idx2]);
        }
    }
}

결과

소스코드 첨부

myTest1.zip