[알고리즘] 선형검색과 이진검색 (누구나 자료구조와 알고리즘 도서 스터디)

 

---

이 포스팅은 '누구나 자료구조와 알고리즘 개정2판' 을 스터디한 내용을 바탕으로 작성하는 공부기록이다.

 

알고리즘

어떤 과제를 완수하는 명령어 집합
어떤 자료 구조를 이미 결정했더라도 코드의 효율성에 영향을 미칠 수 있는 중요한 요인

 

선형 검색

• 왼쪽에서 오른쪽으로 한 번에 한 셀씩 확인하며 값을 찾는 방식
• 원소 수만큼 단계가 필요하다. (N개의 원소가 있을 때 검색에 필요한 단계는 N단계)

이진 검색

• 계속해서 중간 지점을 골라 남은 수 중 반을 제거해 나가며 값을 찾는 방식.
• 정렬된 배열에서만 쓸 수 있다.
• 원소 수를 두 배로 늘릴 때마다 검색에 필요한 단계는 한 단계만 늘어난다. (대단히 효율적인 부분)
• 구현

public static void main(String[] args) {
	// 이진검색 구현 실습
	int[] array = {2, 4, 6, 8, 10, 12, 13};
	System.out.println(binarySearch(array, 8)); // 정렬된 배열 array에서 숫자 8을 찾는데 필요한 단계
		
}
	
public static int binarySearch(int[] arr, int value) {
	int step = 1;
		
	int lower_bound = 0; // 하한선
	int upper_bound = arr.length - 1; // 상한선
	int mid_point = 0;
		
	// 1. 상한선과 하한선의 중간 값을 계속 확인
	while(lower_bound <= upper_bound) {
		mid_point = (upper_bound + lower_bound) / 2;
		
		// 2. 중간지점 값 확인
		if(value == arr[mid_point]) {
			return step; // 값 확인, 현재까지의 단계 반환
		} else if(value < arr[mid_point]) { // 중간 지점 값보다 찾으려는 값이 작을 경우
			upper_bound = mid_point - 1; // 상한선을 중간 지점의 한칸 앞으로 지정
		} else if(value > arr[mid_point]) { // 중간 지점 값보다 찾으려는 값이 큰 경우
			lower_bound = mid_point + 1; // 하한선을 중간 지점의 한칸 뒤로 지정
		}
		step++;
	}
		
	// 3. 상한선과 하한선이 같아질 때까지 검색했는데 없다면 배열에 찾으려는 값이 없는 것 
	return -1;
}

선형 검색과 이진 검색

선형 검색은 y = x 의 그래프를 보이고 이진 검색은 log 의 그래프를 보인다.