이분 탐색
코딩·2025. 10. 10.
이분 탐색 알고리즘을 계속 풀어보는데 바리에이션들이 계속 등장해서 헷갈려서 정리해놓는다.4가지 정도로 구분할 수 있다. 물론 모두 정렬된 배열에서만 동작함기본 이분 탐색정확히 일치하는 값이 있는지 찾는다mid 값이 찾으려는 값과 같은지, 작은지, 큰지를 비교하여 탐색 범위를 절반씩 줄여가는 가장 기본적인 방법이다.while (low Lower Bound, Upper BoundLower Bound는 찾는 값보다 크거나 같은 첫번째 원소의 위치를 찾고 (>=),Upper Bound는 찾는 값보다 큰 첫번째 원소의 위치를 찾는다 (>)while (low = target) { // upper bound이면 > high = mid; // mid가 답일 수 있으므로 포함해서 왼쪽 탐색 } else..
