[문제2]의 PDF는 아래의 링크에 들어가면 된다.
https://kojammin.tistory.com/95
(6)실습6주차_이진탐색+순차자료_[문제1]
[문제1]##이진탐색_순차자료(배열)_노트 :이론 : 시간복잡도 : O(logN) ##코드 : 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354#include stdio.h>#include stdlib.h>#pragma warnin
kojammin.tistory.com
[문제2]
##핵심 개념 :
[문제1]과의 차이점 :
- 제일 큰 Key값을 이진 탐색 => result값이 변하지 않음 => -1로 출력x, N으로 출력(문제 조건이 다름)
- 제일 큰 Key값/제일 작은 Key값 탐색 의 비교 :
- 두 탐색 둘다 START == END 순간은 온다
- 차이점 :
- 제일 큰 Key값 이진 탐색 : Result값이 업데이트 X
- 제일 작은 Key값 이진 탐색 : Result값이 계속 업데이트 O
##입력1,2 직접 해본 노트 :
##코드 :
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
|
#include <stdio.h>
#include <stdlib.h>
#pragma warning (disable : 4996)
int* A = NULL;
int result = -1;
void BinarySearch(int* A, int start, int end,int Key)
{
int n = end + 1;
while (1) {
int mid = (start + end) / 2;
if (A[mid] == Key)
{
result = mid;
return;
}
else if (A[mid] < Key)
{
start = mid + 1;
}
else
{
end = mid - 1;
result = mid;
}
if (start > end) {
//제일 작은 Key && 제일 큰 Key 둘다 start == end 순간은 온다.
//차이점 :
//제인 큰 key일 떄, result가 업데이트 x
if(result==-1) result = n;
//제일 작은 Key일 때, 범위가 줄면서, result 업데이트 o
return;
}
}
}
int main()
{
int N,Key;
scanf("%d %d", &N,&Key);
A = (int*)malloc(sizeof(int) * N);
for (int i = 0; i < N; i++) scanf("%d", &A[i]);
BinarySearch(A, 0, N - 1, Key);
printf(" %d", result);
return 0;
}
|
cs |
'알고리즘(C언어) > 알고리즘 및 실습 강의' 카테고리의 다른 글
(9)실습7주차_이진탐색트리_전위순회,삽입,삭제_이론+코드[문제1] (0) | 2024.09.14 |
---|---|
(8)실습6주차_이진탐색+순차자료_[문제3](작성중) (0) | 2024.09.11 |
(6)실습6주차_이진탐색+순차자료_[문제1] (0) | 2024.09.10 |
(5)실습5주차_합병정렬과 퀵정렬 (0) | 2024.09.05 |
(4)실습4주차_힙과 힙정렬(2)_1_문제1번,문제2번 (0) | 2024.09.05 |