이진탐색

상한가,하한가 구하기 💡 이진 탐색으로 상한가와 하한가를 구해서 원하는 숫자를 출력하자. - 백준 10816번- ‘중복 원수의 개수’ 를 알아내고 싶을 때, 중복 원소의 왼쪽 끝과 오른쪽 끝의 인덱스를 알아내서 계산하면 된다. 이진 탐색 개념을 이용하기에 배열은 사전 정렬 되어있어야 한다. 방법 찾으려는 값의 하한선, 상한선을 따로 구할 생각을 하자. 하한선은 찾으려는 값 이상의 값이 나타난 위치다. “이상” 이란 같거나 큰 수를 뜻한다. 상한선은 찾으려는 값의 초과 값이 나타난 위치다. “초과” 란 보다 큰 수를 뜻한다. 상한가, 하한가 예시 정렬된 배열에서 ‘숫자 10의 상한가, 하한가를 찾는다. (하한선은 최초 10 이 나오는 위치인 3, 상한선은 10을 넘어서는 최초 위치 6 이 나와야 한다.) ..

이진 탐색 💡 이진 탐색은 ‘정렬’ 되어 있는 배열에서 특정 값을 찾는 알고리즘이다. 배열의 중간에 있는 임의의 값을 선택하여 찾으려는 대상 값 x와 비교한다. x가 중간 값보다 작으면 중간 값을 기준으로 좌측 데이터를 비교 x가 중간 값보다 크면 배열의 우측 데이터를 대상으로 다시 검색한다. 동일한 방법으로 다시 중간 값을 임의로 선택하고 비교한다. 이진 탐색 예시 ‘55’ 숫자를 찾아본다. {5, 24, 55, 67, 88, 92, 100} 1️⃣ 첫 번째 시도 먼저 가운데 임의의 값 67을 선택한다. 67 67 > 55 //두 값을 비교한다. = 중간 값 67 보다 작으므로 55은 67의 좌측에 존재함을 알 수 있다. 2️⃣ 두 번째 시도 {5, 24, 55} = 67의 좌측 배열 값을 대상으로 2..