π μ΄μ§ νμμ΄λ?
μ΄μ§ νμ(Binary Search)λ μ λ ¬λμ΄ μλ λ°μ΄ν°κ° μμ λ νμ λ²μλ₯Ό μ λ°μ© μ’νκ°λ©° νμνλ μκ³ λ¦¬μ¦μ΄λ€. μ΄μ§ νμμμλ μμΉλ₯Ό λνλ΄λ λ³μ 3κ°(μμμ , μ€κ°μ , λμ )μ μ¬μ©ν΄, μ°ΎμΌλ €λ λ°μ΄ν°μ μ€κ°μ μμΉμ μλ λ°μ΄ν°λ₯Ό λ°λ³΅μ μΌλ‘ λΉκ΅ν΄μ μνλ λ°μ΄ν°λ₯Ό μ°Ύλλ€. μ΄μ§ νμμ λ°μ΄ν°λ₯Ό μ λ°μ© μ€μ΄λ€λλ‘ λ§λ€κΈ° λλ¬Έμ μκ° λ³΅μλκ° O(logN)μ΄λ€.
// μ¬κ· ν¨μλ‘ κ΅¬ν
int binarySearch(vector<int> &arr, int target, int start, int end) {
if (start > end) return -1;
int mid = (start + end) / 2;
if (arr[mid] == target) return mid;
else if (arr[mid] > target) return binarySearch(arr, target, start, mid-1);
else return binarySearch(arr, target, mid+1, end);
}
// λ°λ³΅λ¬ΈμΌλ‘ ꡬν
int binarySearch(vector<int> &arr, int target, int start, int end) {
while (start <= end) {
int mid = (start + end) / 2;
if (arr[mid] == target) return mid;
else if (arr[mid] > target) end = mid - 1;
else start = mid + 1;
}
return -1;
}
μ½λ©ν μ€νΈμμ μ΄μ§ νμ λ¬Έμ λ νμλ²μκ° ν° μν©μμμ νμμ κ°μ νλ λ¬Έμ κ° λ§λ€. λ°λΌμ νμ λ²μκ° 2,000λ§μ λμ΄κ°λ©΄ μ΄μ§ νμμΌλ‘ μ κ·Όν΄λ³΄λ κ²μ΄ μ’λ€. μ²λ¦¬ν΄μΌ ν λ°μ΄ν°μ κ°μλ κ°μ΄ 1,000λ§ λ¨μ μ΄μμΌλ‘ λμ΄κ°λ©΄ μ΄μ§ νμκ³Ό κ°μ΄ O(logN)μ μλλ₯Ό λ΄μΌ νλ μκ³ λ¦¬μ¦μ λ μ¬λ €μΌ λ¬Έμ λ₯Ό ν μ μλ κ²½μ°κ° λ§λ€. λ μ΄λ° λ¬Έμ μ κ²½μ° μ λ ₯λ°λ λ°μ΄ν°μ μμ΄ λ§μ΄ μκ°μ΄κ³Όκ° λ μ μμΌλ μ μνκΈΈ λ°λλ€.
c++μμλ μλ μ½λλ₯Ό main() μμ λ£μ΄μ£Όλ©΄ λλ€.
ios::sync_with_stdio(false);
cin.tie(NULL);
νμ΄μ¬μμλ input() λμ sys λΌμ΄λΈλ¬λ¦¬μ readline()λ₯Ό μ΄μ©νλ©΄ λλ€.
import sys
input_data = sys.stdin.readline().rstrip()