[코스모스 4주차] 이분탐색 알고리즘

1. 이분탐색?

• 이분 탐색은 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법
• 이분 탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있음
• 변수 3개(start, end, mid)를 사용하여 탐색
• 찾으려는 데이터와 중간점 위치에 있는 데이터를 반보적으로 비교해서 원하는 데이터를 찾는 것이 이진탐색의 과정
• 시간 복잡도 : O(log₂N)
• 예를들어, 처음 데이터의 개수가 32개라면, 이론적으로 1단계를 거치면 약 16개의 데이터가 남고, 2단계에서 약 8개, 3단계에서 약 4개의 데이터만 남게됨
• 이진 탐색은 탐색 범위를 절반씩 줄이고, O(log₂N)의 시간복잡도를 보장

---

2. 이분탐색 알고리즘

https://www.acmicpc.net/problem/1920

1920번: 수 찾기

'수 찾기' 백준 문제를 풀며 이분탐색 알고리즘에 대해 알아보자

 

 

 

JAVA 언어로 풀이를 해보자

• Scanner sc = new Scanner(System.in)로 입력을 받음
• 정수 N값을 입력 받고, 배열의 크기로 사용
• 크기가 N인 정수 배열을 선언
• N번 반복하면서 사용자로부터 정수를 입력받아 배열 arr에 저장함
• 배열 arr을 정렬
• 찾고자 하는 값의 개수를 입력 받고, M번 반복하면서 찾고자 하는 값에 대한 검색 수행
• 각 반복마다 찾을 값과 답을 저장할 변수, 이진 검색을 위한 시작과 끝 인덱스를 초기화
• 이진 검색 수행
• 배열을 반씩 나누어 검색 범위를 줄여나감
• 찾고자 하는 값과 현재 중간 값이 일치하면 answer를 1로 설정하고 반복을 종료함
• 검색 결과 출력하고, 만약에 찾고자 하는 값이 배열에 존재하면 1, 아니면 0을 출력함