본문 바로가기
반응형

binary search2

[Python] 백준 1920번 - 수 찾기 https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 문제 N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에.. 2022. 10. 20.
[Python][이코테] 이진 탐색 이진 탐색 Binary Search 이진 탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다. 이미 정렬되어 있다면 매우 빠르게 데이터를 찾을 수 있다는 특징이 있다. 이진 탐색은 탐색 범위를 절반씩 좁혀가며 데이터를 찾는 방법이다. 이진 탐색은 변수 3개를 사용한다. 시작점, 끝점 그리고 중간점 예를들어 0 2 4 6 8 10 12 14 16 18 의 배열에서 4를 찾는다고 가정하자 0 2 4 6 8 10 12 14 16 18 우선 시작점은 [0], 끝점은 [9] 중간점은 9/2 = 4.5 에서 소수점은 버려서 [4]로 지정한다. [0] = 0, [9] = 18, [4] = 8 [4]의 데이터와 찾으려는 값 4를 비교한다. [4]의 값이 더 크므로 중간점 이후의 값은 확인할 필요.. 2022. 10. 13.
반응형