이진 검색 (10816번, 1920번)

배열의 중간 위치의 값과 key값을 비교하여 찾아가는 방식

	public static int binarySearch (int[] arr, int key) { 		 		int lo = 0; 		int hi = arr.length-1; 		 		while(lo<=hi) {         	//중간 인덱스(mid) while 문이 반복될 때마다(검색할때마다) lo hi를 참조 			int mid = (lo+hi)/2;             //찾고 싶은 key 값이 검색 배열 중앙의 값보다 작을 경우 			if(arr[mid] > key) {             //다음 검색 배열의 끝 인덱스 값을 배열 중앙의 값보다 1작은 값으로  				hi = mid-1;             //찾고 싶은 key 값이 검색 배열 중앙의 값보다 클 경우 			} else if(arr[mid] < key){             //다음 검색 배열의 첫 인덱스 값을 배열 중앙의 값보다 1 큰 값으로 				lo=mid+1; 			} else {             //같으면 key 값과 검색 배열 중앙값이 같으면 1 리턴 				return 1; 			} 		} 		return 0; 	}

 

자료 구조와 알고리즘 공부는 이전에 책을 했었지만 직관적으로 이해하기 어려운 부분은 대부분 핵심 로직보다는 나머지 로직?이었다. 예를 들어 이진 검색은 위와 같은 검색할 배열의 양끝 인덱스 값을 중강 인덱스 값으로 치환하면서 진행하는 알고리즘이다.  위 코드의 주석들과 같이 핵심 로직은 이해하기 쉽다. 그러나 내가 알고리즘이 어려운 주된 이유는 생각만으로는 검색 배열의 길이가 3이 되고 2가 되고 1일 되었을 때 lo hi값이 어떻게 될지, 어떤 때 lo 값이 hi 값을 넘게 되는지와 같이, 로직에서 주변부?같은 부분이 바로 머리로는 그려지지 않아 실제로 그려보거나 예시들을 하나 하나 정리해봐야 이해가 된다는 점이다. 나만 그런가.. 하지만 다른 개발 블로그의 도움으로 직접 할 수고는 많이 덜고 있고 감사하게 생각한다.

[백준] 10816번 : 숫자 카드 2 - JAVA [자바]

https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카..

st-lab.tistory.com