[스터디] 검색 알고리즘

데이터 집합이 존재할때 '검색만 하면 되지!' 라고 생각한다면 검색에 사용할 알고리즘은 계산 시간이 짧은 것을 선택하면 됩니다.

 

하지만 데이터 집합에 대한 검색뿐만 아니라 데이터의 추가  , 삭제  등을 자주하는 경우라면 검색 이외의 작업에 소요되는 비용을 종합적으로  평가하여 알고리즘을 선택 해야 합니다.

 

 

선형 검색

배열에서의 검색은 원하는 키 값을 갖는 요소를 만날 때까지 맨 앞부터 순서대로 요소를 검색하는 알고리즘 입니다.

 

 

이진 검색

이진검색은 선형 검색보다 훨씬 빠른속도로 검색을 할 수 있습니다.

 

 

 

이 알고리즘을 사용하기 위해서는 전제 조건이 있습니다.

- 오름차순 또는 내림차순으로 정렬된 데이터

 

 

 

 

여러분들은 영어사전을 검색할때 어떤식으로 찾나요?

 

1. 사전 처음부터 y라는 단어가 나올때까지 찾는다.

 

2. 사전의 가운데를 펼치고 펼친곳의 알파벳의 순서를 확인하고 목표를 찾아간다.

 

대부분 아니 거의 전부가 2번을 방법을 선택하겠죠? 

 

저희는 어릴적부터 이진 탐색을  몸소 실천하고 있었습니다.

 

 

 

 

 

쉽게 사용하는 이진검색

 

JAVA는 배열에서 이진 검색을 하는 메서드를 표준 라이브러리로 제공합니다.

이진 검색 표준 라이브러리의 세서드로는 Java.util.Arrays 클래스의 binarySearch 메서드가 있습니다.

 

• 장점1. 이진 검색 메서드를 코딩 할 필요 X
• 장점2. 모든 자료형 배열에서 검색이 가능

 

메소드 확인방법

https://docs.oracle.com/javase/7/docs/api/

Java Platform SE 7

->  Java.util.Arrays ->  binarySearch

 

 

 

 

예제

package AlgorithmStudy.검색.이진탐색.수찾기_1920;

import java.util.Arrays;
import java.util.Scanner;

public class BinarySearchTester {
	
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		System.out.println("몇개의 데이터를 넣겠습니까? ");
		int num = scan.nextInt();
		int[] x = new int[num];
		
		System.out.println("오름차순으로 입력하세요");
		
		System.out.print("x[0] :");
		x[0] = scan.nextInt();
		
		for (int i = 1; i < num; i++) {
			do {
				System.out.print("x[" + i + "] : ");
				x[i] = scan.nextInt();
			}while(x[i] < x[i-1]);
		}
		
		
		System.out.println("검색할 값 : ");
		int key = scan.nextInt();
		
		
		int idx = Arrays.binarySearch(x, key);
		
		if(idx < 0) {
			System.out.println("그 값의 요소가 없습니다.");
		}else {
			System.out.println("key 는 " + idx +" 번 인덱스에 존재합니다." );
		}
		
		
		
	}

}

 

결과

실패

 

검색 성공 -> key와 일치하는 인덱스 반환

검색 실패 ->  -x-1

 

 

 

성능

단순검색	이진 탐색
64개 -> 64번	64개 ->  6번
40억 -> 40억	40억 -> 32번
O(n)	O(Log n)
선형시간	로그시간