이분 탐색 & Upper Bound, Lower Bound 개념 정리
1. Binary-Search란 무엇인가요?정렬된 배열 혹은 List 에서 탐색 구간을 절반씩 줄여가며 특정 값을 찾는 탐색법이다. 다음과 같이 진행 된다.(0) 기본적인 용어는 다음과 같다.target: 찾고자 하는 값, start : 왼쪽 포인터,(index=0에서 시작), end: 오른쪽 포인터(배열 끝에서 시작), mid: 두 값의 중간에 위치한 값(1) mid를 구하고 target 값과 대소관계를 비교한다.(2) mid > target 이면, mid 값이 target값으로 향하도록, end = mid-1 로 탐색 영역을 절반 줄인다.(3) mid target 이면, start = mid +1 이 되도록 하여, 탐색 영역을 절반 줄인다.(4) mid == target 이면 값을 구했으므로, 이분 ..
더보기
