정리하고기록하자

Lower_bound Lower_bound는 하한선 이라는 뜻이다. 찾고자 하는 Key 값 보다 크거나 같은 첫 번째 인덱스를 찾아주는 알고리즘이다. 이를 활용하면 원하는 Key 값이 없어도 이에 가장 가까운 데이터의 위치를 찾을 수 있다. Lower_bound는 Key 값보다 크거나 같은 원소의 위치(이상)를 찾는 것이기 때문에 mid의 값이 Key보다 작을 때는 left를 mid + 1로 변경해 주고 ( if( arr[mid] < Key) left = mid +1 ) Key보다 크거나 같을 때는 right를 mid로 변경하여 ( else right = mid ) Key 값을 포함시키도록 한다. Lower_bound : 일치하는 숫자가 처음 나타나는 지점 public class Lower_bound {..

이진 탐색 개념과 원리 정렬된 상태의 입력 데이터에 대한 효과적인 탐색 방법이다. 오름차순으로 정렬되었다고 가정되었을때 탐색 방법 배열의 가운데 원소 A[mid]와 탐색키 x를 비교한다. 탐색키 = 가운데 원소 => 탐색 성공 ( 인덱트 mid 반환 후 종료 ) 탐색키 이진탐색 ( 원래 크기 1/2 인 왼쪽 부분배열 ) 순환 호출 탐색키 > 가운데 원소 => 이진탐색 ( 원래 크기 1/2 인 오른쪽 부분배열 ) 순환 호출 *이진탐색 ( 원래 크기 1/2 인 왼쪽 부분배열 ) / 이진탐색 ( 원래 크기 1/2 인 오른쪽 부분배열 ) 탐색을 반복할 때마다 대상 원소의 개수가 1/2씩 감소 한다. 분할 배열의 가운데 원소를 기준으로 왼쪽과 오른쪽 부분배열로 분할한다. 탐색키와 가운데 원소..