본문 바로가기

이분 탐색1

[이분 탐색] 이분 탐색(Binary Search) 이란 ? 이분 탐색 두 이, 나눌 분을 써서 이분인가? 정답, 이분 탐색은 두개로 나누어서 탐색하는 것이다. 예를 들어, 1부터 10까지 있다고 생각해보자. {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} 우리가 8을 찾을 때, 눈으로 바로 보이니까 위치를 파악할 수 있다. 하지만 몇 번째에 있는가? 배열은 0번째부터 시작하니 7번째에 있다는 것을 알 수 있다. 컴퓨터 배열 인덱스 개념이 없는 사람들은 8번째라고 답할 것이다. 즉, O(1) 시간이다. 그럼, {1, 4, 7, 10, 12, 23, 30, 35, 100, 120} 이 있을 때, 35의 위치는? 우리는 앞에서 값을 세어가면서 몇 번째에 있는지 알 것이다. 즉, O(N) 시간이다. 100만개의 숫자가 있다면? 우리는 100만개를 일일이 세다가.. 2024. 2. 1.

이전 1 다음

티스토리툴바