Search Algorithm - 검색 알고리즘

Search Algorithm - 검색 알고리즘

• 정렬(오름/내림차순)되어있는 데이터를 이진 검색(이분 탐색)을 사용해 반씩 나눠 검색한다.
• low값과 high값이 만날 때 까지 반복하는 while반복문을 활용하고,
• 포인터 역할을 하는 중간 값((low+high)/2)을 mid변수로 선언하고 찾는 값(search 변수)과 비교하는 if문을 작성한다.
• 찾을 데이터 값이 mid값보다 크면 low = mid+1
  찾을 데이터 값이 mid값보다 작으면 high = mid-1 

package searchAlgorithm;

//[?] 정렬되어 있는 데이터를 이진 검색(이분 탐색)을 사용해 반씩 나눠 검색.

//검색 알고리즘(Search Algorithm) : 주어진 데이터에서 특정 데이터 찾기
public class SearchAlgorithm {

	public static void main(String[] args) {
		//[1] input
	
		int[] data = {1,3,5,7,9};	//오름차순 정렬되었다고 가정
		int N = data.length;	 	//의사 코드 정의
		boolean flag = false;
		int index = -1; 		//찾은 위치(인덱스)
		int search = 9; 		//찾을 데이터
		
		//[2] process : 이진 검색 (개념적으로 full scan이라기 보단 index scan이라고 볼 수 있음)
		int low = 0; 			//min : 가장 낮은 인덱스
		int high = N-1;			//max : 가장 높은 인덱스
		while(low <= high) {
			int mid=(low+high)/2; 	//mid(중간) 인덱스 설정 : mid가 포인터 역할을 수행
			if(data[mid]==search) {	//mid값이 찾는 값이면, 
				flag = true;	//찾았다! 깃발 들고,
				index = mid;	//위치값을 mid값으로!
				break;
			}
			//
			if(data[mid]<search) {
				low = mid+1;	// 찾을 데이터가 mid보다 크면 오른쪽 영역으로 이동
			} else {
				high = mid -1; 	// 찾을 데이터가 mid보다 작으면 왼쪽 영역으로 이동
			}
		}
		
		//[3] output
		if (flag) {
			System.out.println(search+"를 "+index+"위치에서 찾았습니다.");
		} else {
			System.out.println("찾지 못했습니다.");
		}
	}
}