1920番-数値の検索(c++)
8444 ワード
🗒 1920題
📌 バイナリ検索アルゴリズムを使用して数値を検索\
1️⃣ 일반 for문을 사용해서 수를 찾을 경우, '시간 초과'가 발생 -> binary Search 사용하자
2️⃣ 이진 검색 알고리즘이란?
'오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘'
처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식을 채택
3️⃣ 정렬된 첫 번째 array와 두 번째 array를 비교한다 -> binary Search를 사용하여
4️⃣ low값보다 high값이 작을 때까지 loop를 돌면서 두 번째 array 원소와 같은 걸 찾는다
5️⃣ low, high, mid 사용해서 key 값 비교 -> 없으면 0, 있으면 1 return
➰コード表示の1920➰
#include <cstdio>
#include <algorithm>
using namespace std;
int firstArr[100001];
int secondArr[100001];
int binarySearch(int num, int key) {
int low = 0, high = num - 1, mid;
while (low <= high) {
mid = (low + high) / 2;
if (firstArr[mid] == key)
return 1;
else if (firstArr[mid] > key)
high = mid - 1;
else
low = mid + 1;
}
return 0;
}
int main() {
int fnum = 0, snum = 0;
scanf("%d", &fnum);
for (int i = 0; i < fnum; i++)
scanf("%d", &firstArr[i]);
scanf("%d", &snum);
for (int i = 0; i < snum; i++)
scanf("%d", &secondArr[i]);
sort(firstArr, firstArr+fnum);
for (int i = 0; i < snum; i++) {
if (binarySearch(fnum, secondArr[i]))
printf("1\n");
else
printf("0\n");
}
return 0;
}
Reference
この問題について(1920番-数値の検索(c++)), 我々は、より多くの情報をここで見つけました https://velog.io/@yoonah-dev/1920번-수-찾기cテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol