[알고리즘 독학] 검색 알고리즘 개념(2)

이진 검색

 

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

 

package search;

import java.util.Scanner;

public class Ex03 {

		static int binSearch(int[] a, int n, int key) {
			int pl = 0;
			int pr = n-1;
			
			do {
				int pc = (pl + pr)/2;
				if(a[pc] == key) return pc;
				else if(a[pc] < key) pl = pc + 1;
				else pr = pc - 1;
			} while (pl <= pr);
			
			return -1;
			
		}

	
	public static void main(String[] args) {
		
		Scanner stdIn = new Scanner(System.in);
		
		System.out.print("요소수: ");
		int num = stdIn.nextInt();
		int[] x = new int[num];
		
		
		System.out.println("오른차순으로 입력하세요");
		
		System.out.print("x[0] : ");
		x[0] = stdIn.nextInt();
		
		for(int i = 1; i < num; i++) {
			do {
				System.out.print("x[" + i + "] : ");
				x[i] = stdIn.nextInt();
			} while(x[i] < x[i-1]);
		}
		
		System.out.print("검색할 값 : ");
		int ky = stdIn.nextInt();
		
		int idx = binSearch(x, num, ky);
		
		if(idx == -1) {
			System.out.print("그 값의 요소가 없습니다.");
		} else {
			System.out.print(ky + "은(는) x[" + idx + "]에 있습니다.");
		}
		
	}

}

 

 

복잡도

프로그램의 실행 속도는 프로그램이 동작하는 하드웨어나 컴파일러 등의 조건에 따라 달라집니다.

 

복잡도 요소

1. 시간 복잡도 : 실행에 필요한 시간을 평가하는 것

2. 공간 복잡도 : 기억 영역과 파일 공간이 얼마나 필요한가를 평가하는 것

 

기본 자료형 배열에서 binarySearch메서드로 검색하기

binarySearch(Object[] a, Object key) : 자연 정렬이라는 방법으로 요소의 대소관계를 판단

binarySearch(T[] a, Comparator<? super T> c) : 자연 정렬이 아닌 순서로 줄지어 있는 배열을 검색하여 판단