99클럽 코테 스터디 36일차 TIL + 이진 탐색(Binary Search)(1)

학습 키워드

- 이진 탐색(Binary Search)

 

공부한 내용

이진 탐색(Binary Search)

• ‘정렬된 배열’에서 ‘특정 값’을 찾는 알고리즘을 의미한다.
• 이진탐색은 ‘탐색 범위를 절반씩 줄여’나가기 때문에 선형탐색에 비해 빠른 속도를 보장한다. 하지만 배열이 정렬되어 있어야 한다는 조건이 필요하기 때문에 배열이 정렬되어 있지 않은 경우에는 정렬작업이 필요하다.
• 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾는 방식이다.

예) 크기가 100인 배열이 있고, 우리가 찾고자 하는 값이 99번째 인덱스에 들어있는 상황을 가정해 보자.

• 일반적인 반복문을 사용하여 1부터 100까지 반복하면 99번째 반복에서 찾고자 하는 값을 찾을 수 있다. 물론 이 경우 찾고자 하는 데이터가 앞쪽에 있다면 같은 데이터셋에 대하여 탐색 시간이 이분탐색을 이용했을 때보다 빠를 것이다.
• 그런데 만약 데이터의 크기가 1억 개이고, 운이 나쁘게도 우리가 찾고자 하는 값이 99,999,999 번째의 데이터인 경우에는 시간이 매우 오래 걸릴 것이다.

⇒ 이진탐색을 이용하면 데이터의 위치에 따른 탐색시간의 격차를 줄일 수 있다.

⇒ 정렬된 배열 또는 리스트에 적합한 고속 탐색 방법이다.

선형탐색(Linear Search) 이란?

• 배열(Array)이나 리스트(List)와 같은 데이터 구조에서 특정한 값을 찾는 알고리즘 중 하나이다.

이진탐색 과정

• 배열(데이터셋)의 ‘중간 값’을 선택하여 찾고자 하는 값과 비교한다.
• 만약 중간 값이 찾고자 하는 값보다 크면 ‘배열 왼쪽 부분’에서 탐색을 진행하고, 값보다 작으면 ‘배열 오른쪽 부분’에서 탐색을 진행한다.
• 이 과정에서 찾고자 하는 값이 나올 때까지 반복한다.

→ 중앙값 > 타깃 데이터 인 경우 : 중앙값을 기준으로 왼쪽 데이터셋을 선택한다. (오른쪽은 버린다.)

→ 중앙값 < 타겟 데이터 인 경우 : 중앙값을 기준으로 오른쪽 데이터셋을 선택한다. (왼쪽은 버린다.)

⇒ 계속 반복하다가 중앙값 = 타겟 데이터 일 때 탐색을 종료한다.

• 데이터는 항상 정렬되어 있어야 한다.

이진 탐색과 for문(선형 탐색)의 차이점

• 일반적으로 이진 탐색을 이용하여 값을 찾는 방법이 for문을 이용하는 것보다 빠르다.
• 이진 탐색은 정렬된 배열에서 원하는 값을 찾는 알고리즘이며, 중간값을 찾아 탐색 범위를 반으로 줄이면서 값을 찾아간다.
• 이에 비해 for문은 배열 전체를 순회하면서 값을 찾기 때문에, 배열의 크기와 상관없이 속도가 일정하게 증가한다.

이진 탐색의 사용처

• 이진 탐색은 데이터가 오름차순으로 정렬되어 있을 때 특정한 값을 찾아야 할 때 사용한다.
• 데이터의 양이 많을 경우에도 빠른 시간 내에 값을 찾을 수 있어 많이 활용된다.

이진 탐색의 성능

• 이진탐색의 경우 시간 복잡도의 '빅오 표기법'을 이용하여 확인하였을때 로그 시간인 O(logn)으로써 다른 정렬에 비해 상대적으로 매우 빠르다.

 

 

 

참고 자료

- https://adjh54.tistory.com/187#google_vignette

- https://innovation123.tistory.com/65