이진탐색

 이진 탐색(binary search)는 정렬되어 있는 자료들의 집합에서 특정 자료를 찾고자 할 때 많이 사용되며 매우 빠른 탐색 알고리즘이다. 이진 탐색은 '퀵정렬'과 유사하게 '분할 후 정복(divide and conquer)'의 전략을 사용한다. 이 전략을 사용하는 알고리즘은 문제를 나누어 해결해 나가는 방법이기 때문에 실행시간은 log의 설징을 갖는다. 특히 문제의 크기를 정확히 양분하는 경우에는 최악의 경우라고 logN의 성능을 보장한다.

 이진 탐색의 탐색 시간은 'T = K * logN'으로 O(logN)이다. 선형 탐색의 시간보다 상당히 빠르지만 이진 탐색은 반드시 정렬이 되어있어야 한다. 그러므로 정렬되지 않는 리스트의 경우에는 정렬하는 비용 또한 상당히 들 것이다. 이와 같은 단점에도 불구하고 다음과 같은 상황에서 이진 탐색은 효율적인 성능을 제공한다.

 1) 새로운 자료가 추가되었어도 모든 자료가 재정렬이 일어나지 않는 경우 -> 해싱, 인덱스를 이용하는 경우

 2) 획기적으로 빠르고, 효율적인 자료의 재정렬이 가능한 자료 구조를 사용할 경우 -> B-트리 계열의 트리 구조 사용


다음은 이진 탐색의 JAVA 소스이다.

package Search;

public class BinarySearch {
	public static void main(String[] args) {
		int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };

		binarySearch(2, arr);
	}

	public static void binarySearch(int iKey, int arr[]) {
		int mid;
		int left = 0;
		int right = arr.length - 1;

		while (right >= left) {
			mid = (right + left) / 2;

			if (iKey == arr[mid]) {
				System.out.println(iKey + " is in the array with index value: " + mid);
				break;
			}

			if (iKey < arr[mid]) {
				right = mid - 1;
			} else {
				left = mid + 1;
			}

		}
	}
}


+

기술면접에서 이진탐색을 왜 구현하지 못했을까... 자료구조 시간에 그렇게 공부하고 이해하고 구현하고 다 해본 것을ㅠㅠ

기본을 먼저 보고 갔어야 하는 건데, 괜히 다른 알고리즘을 너무 보고 갔더니 간단한 알고리즘조차 어렵게만 생각하고 복잡하게 풀려고 한 것 같다.. 그래서 다시 기본기를 훑어보고자 이렇게 블로그에 남겨놓는다.

'대학 생활 > JAVA' 카테고리의 다른 글

[JAVA] 기수정렬(RadixSort)  (0) 2015.11.20
[JAVA] 피보나치 - 재귀사용  (0) 2015.11.13
[JAVA] 퀵정렬(QuickSort)  (0) 2015.11.06
[JAVA] 딕스트라 최단경로(Dijkstra Shortest Paths)  (0) 2015.10.31
/* squential search, binary search
   단어 찾기 프로그램
	작성자 : 김영준
	날짜 : 2013/10/3
*/
#include <stdio.h>
#include <string.h>

// 전역선언
typedef struct words {
	char words[30];	// 파일중 제일 긴 단어 22자
} Words;

const int MAX_SIZE = 26000;

// 기본형선언
void readWords(Words* wordsArray, int* last);
void seqSearcah(Words wordsArray[], int last); 
void binarySearch(Words wordsArray[], int last);

int main(void) {
// 지역정의 
	Words wordsArray[MAX_SIZE];
	int last = 0;

// 문장들
	readWords(wordsArray, &last);
	seqSearch(wordsArray, last);
	printf("\n");
	binarySearch(wordsArray, last);
	return 0;
} // main

/* ================= readWords =================
	파일을 읽어서 배열에 적재한다.
	사전조건		wordsArray는 채워져야 할 배열
				last는 마지막 요소의 인덱스
	사후조건		배열이 채워짐
*/
void readWords(Words* wordsArray, int* last) {
// 지역변수
	char buf[256];
	FILE* fp = fopen("/usr/dict/words", "r");

// 문장들
	if(fp == NULL) {
		printf("File is null\n");
		exit(1);
	}

	printf("단어 읽는 중");
	while(fgets(buf, sizeof(buf), fp) != NULL) {
			//개행문자 삭제
			buf[strlen(buf)-1] = 0;
			// 문자열 복사 함수 strcpy() 사용.
			strcpy(wordsArray[*last].words, buf);
			(*last)++;
			if(*last % 1000 == 0) {
				printf(".");
			}
	}
	printf("%d 단어의 사전 구축 완료\n", *last);
	fclose(fp);
} // readWords

/* ================= seqSearch =================
	순차적 찾기로 목표를 찾는다.
	모두 찾고나면 결과를 출력한다.
	사전조건		wordsArray는 데이터를 가지고 있는 배열
				last는 마지막 요소의 인덱스
*/
void seqSearch(Words wordsArray[], int last) {
	int looker;
	char target[256];

	printf("영어 단어 찾기(Sequential Search)\n");
	printf("==================================\n");

	while(1) {
		looker = 0;
		printf("단어 입력(quit:ESC) : ");
		fgets(target, sizeof(target), stdin);
		// 개행문자 삭제
		target[strlen(target)-1] = 0;

		if(target[0] == 27){
			printf("Program quit...\n");
			break;
		}

		// seqSearch
		while(looker < last && strcasecmp(target, wordsArray[looker].words)) {
			looker++;
		}

		// 결과 출력
		if(!strcasecmp(target, wordsArray[looker].words)) {
			printf("단어 %s 찾음 비교횟수 : %d\n", target, looker+1);
		} else {
			printf("단어 %s 찾기실패 비교횟수 : %d\n", target, looker+1);
		}
	}

	printf("==================================\n");
	printf("Sequential search 끝\n");

} // seqSearch

/* ================= binarySearch =================
	이진 찾기로 목표를 찾는다.
	모두 찾고나면 결과를 출력한다.
	사전조건		wordsArray는 데이터를 가지고 있는 배열
				last는 마지막 요소의 인덱스
*/
void binarySearch(Words wordsArray[], int end) {
// 지역변수
	int looker;
	char target[256];
	int first, mid, last;
	int cnt = 0;

// 문장들
	printf("영어 단어 찾기(binary Search)\n");
	printf("==================================\n");
	
	while(1) {
		looker = 0;
		first = 0;
		last = end;
		cnt = 0;

		printf("단어입력(quit:ESC) : ");
		fgets(target, sizeof(target), stdin);
		// 개행문자 삭제
		target[strlen(target)-1] = 0;

		if(target[0] == 27) {
			printf("Program quit...\n");
			break;
		}

		// binarySearch
		while( first <= last) {
			mid = (first + last) / 2;
			if(0 < strcasecmp(target, wordsArray[mid].words)) {
				first = mid + 1;
			} else if(0 > strcasecmp(target, wordsArray[mid].words)) {
				last = mid - 1;
			} else {
				break;
			}
			cnt++;
		}

		// 결과 출력
		if(!strcasecmp(target, wordsArray[mid].words)) {
			printf("단어 %s 찾음 비교횟수 : %d\n", target, cnt+1);
		} else {
			printf("단어 %s 찾기실패 비교횟수 : %d\n", target, cnt+1);
		}

	}

	printf("==================================\n");
	printf("Sequential search 끝\n");
} // binarySearch


+ Recent posts