[문제해결기법] 7. 이분 탐색
1. 탐색 오름차순으로 정렬된 N개의 정수 배열 A[0], ..., A[N-1]이 있다. X가 주어졌을 때, A[i] = X라면 i를 리턴하는 함수 find(N, X)를 작성하시오. 이 함수는 내부적으로 compare(i, val)을 호출하는데, 이는 A[i]=val이면 0, A[i] val이면 -1을 리턴하는 함수이다. N은 최대 100이다. int find(int sub, int N, int X) { int start = 0, end = N-1, t; while (start 0) start = mid + 1; // 기준값보다 작으면 start를 당기기 else if (v) end = mid - 1; // 기준값보다 크면 end를 당기기 else return mid; }..
[C++/BOJ] 13423 : Three Dots (이진탐색) / 삽질 기록
https://www.acmicpc.net/problem/13423 문제 직선 위에 서로 다른 N개의 점이 찍혀 있다. 점 i의 위치는 Xi이다. N개의 점 중 3개를 골라 가장 왼쪽에 있는 점을 a, 가운데 있는 점을 b, 가장 오른쪽에 있는 점을 c라고 하자. 각각의 점의 위치는 Xa, Xb, Xc이다. 이때 점 a, b 사이의 거리와 점 b, c사이의 거리가 같으면 세 점의 간격이 같다고 한다. 즉, Xb - Xa = Xc – Xb일 때 세 점의 간격이 같다. 다음은 N = 5인 경우의 예시이다. 위 예시에서 점의 위치는 각각 -4, -1, 0, 2, 4이다. 이중 -4, -1, 0위치의 세 점을 각각 a, b, c라고 하면 Xb - Xa = 3, Xc – Xb = 1로 간격이 같지 않다. 그러나 ..
