글 읽기 - 이렇게 하면 왜 안될까요?

(追記) (追記ここまで)

이렇게 하면 왜 안될까요?

1920번 - 수 찾기

cesmark376 9달 전 0

이런 방식으로 이분탐색을 구현하면 안 되는 이유가 뭐인지 모르겠습니다.

#include <bits/stdc++.h>
using namespace std;
int main() {
 ios_base::sync_with_stdio(false);
 cin.tie(0); cout.tie(0);
 
 int n, m, k;
 cin >> n;
 vector<int> v(n);
 for(int i = 0; i < n; i++)
 cin >> v[i];
 sort(v.begin(), v.end()); 
 
 cin >> m;
 while(m--) {
 cin >> k;
 int lo = 0, hi = n - 1, chk = 0;
 while(lo + 1 < hi) {
 int mid = (lo + hi) / 2;
 if(v[mid] == k) {
 chk = 1;
 break;
 }
 if(v[mid] < k)
 lo = mid;
 else
 hi = mid; 
 }
 if(lo == k || hi == k)
 chk = 1;
 cout << chk << '\n';
 }
 
 return 0;
}

sianke1991 9달 전 0

배열의 길이 n이 1일 경우

19 라인의 while loop를 돌지 않게 됩니다.

30 번째 라인, lo와 hi는 인덱스 값이므로

실제 찾으려는 값인 k와 비교하는 것은 알맞지 않는 것 같습니다.

댓글을 작성하려면 로그인해야 합니다.

(追記) (追記ここまで)

Baekjoon Online Judge

채점 현황

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

사업자 등록 번호: 541-88-00682
대표자명: 최백준
주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
전화번호: 02-521-0487 (이메일로 연락 주세요)
이메일: contacts@startlink.io
통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)

문제

문제

출처

ICPC

이렇게 하면 왜 안될까요?

cesmark376 9달 전 0

sianke1991 9달 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말