이분탐색

[Baekjoon] 10815 숫자 카드

✉️문제 https://www.acmicpc.net/problem/10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 📝 접근 이분 탐색을 이용한다. 이분 탐색의 핵심은 left point와 right point를 선언한다음 이를 계속 업데이트하는 것이다. 🗝 문제풀이 package baekjoon; import java.util.Arrays; import java.util.Scanner; public class B10815 { static int n,m; static in..

[알고리즘] 이분 탐색(Binary Search)

이분 탐색이란? --> 정렬되어 있는 배열에서 데이터를 찾을 때 배열의 길이를 1/2만큼 줄이면서 탐색하는 방법이다. 아래와 같이 1에서 10까지의 숫자가 있는 배열이 있다고 해보자. 여기서 8을 이분 탐색으로 찾아보자. 먼저 가운데 지점을 찾는다. 이 때 left, right값을 1과 10으로 지정한 후 찾게 된다. 가운데 값과 target값(8)의 크기를 비교한다. 만약 가운데 값이 타겟 값보다 크다면 right = mid - 1로 바꿔준다. 만약 가운데 값이 타겟 값보다 작다면 left = mid + 1로 바꿔준다. 그 다음 가운데 지점을 갱신해준 뒤 가운데 값과 타겟 값을 비교한다. int binary_search(int target, int n) { int result = 0; int left ..