이진 탐색 형태 :
#include <stdio.h>
#include <stdlib.h>
// 여기서부터 작성
int N, T;
int arr[50001]; //50,000개의 데이터
int bsearch(int s, int e, int d) {
int m;
while (s <= e) {
m = (s + e) / 2;
//중앙값보다 같으면 성공 위치 리턴
if (arr[m] == d) {
return m + 1;
}
//중앙값보다 크면 오른쪽 영역 재탐색
else if (arr[m] < d) {
s = m + 1;
}
//중앙값보다 작으면 왼쪽 영역 재탐색
else if (arr[m] > d) {
e = m - 1;
}
}
//못 찾은 경우 리턴 0
return 0;
}
int main(void)
{
// freopen("input.txt", "r", stdin);
int i, data;
scanf("%d", &N);
for (i = 0; i < N; i++) {
scanf("%d", &arr[i]);
}
scanf("%d", &T);
for (i = 0; i < T; i++) {
scanf("%d", &data); //찾을 데이터
printf("%d\n", bsearch(0, N - 1, data));
}
return 0;
}이진 탐색 문제 :
[정올 2851] 예산
문제 풀이 : https://gudwns999.tistory.com/106
:이진탐색의 범위를 정하고 (s는 0 e는 예산액 중 MAX값) 총액에 만족할 때 까지 mid 값을 이진탐색 한다. 이 때 주의 해야 할 점은 문제에 따라 예산의 합계가 정수 범위를 넘어 갈 수 있기 때문에 문제 조건을 잘 보고 int로 선언할 지 long long int로 선언할지 정해야 한다.
[정올 2788] 도약
문제 풀이 : https://gudwns999.tistory.com/107
: 3중 포문 풀이와 이진 탐색 풀이가 있는데 이진 탐색이 압도적으로 성능이 좋다.
이진탐색의 경우 2중 포문 안에 이진 탐색이 있는데 1중 포문에서 첫번째 점프 시작 위치를 돌아가며 시도하고 2중 포문에서 첫번째 점프가 도착하는 지점( = 두번째 점프의 시작 지점)을 정한 뒤 이진탐색으로 두번째 점프가 도착하는 지점을 탐색 하면 된다.
[백준2805] 나무 자르기
원본 출처 : https://www.acmicpc.net/problem/2805
문제 풀이 :
: 예산 문제와 같은 개념의 문제이다. 예산은 최대한 많은 예산을 줘야 했고 나무는 적어도 얼마나 들고 가면 되냐 하는 문제이다. 입력되는 값이 크기 때문에 long long 을 써주어야 한다.