[알고리즘 공부] 자바스크립트 이진 탐색(binary search) #1

☘️ 이진 탐색

이진 탐색 정의

이진 탐색은 정렬된 요소들을 절반씩 줄여가며 찾는 알고리즘이다. 

 

이진 탐색

이진 탐색
정렬이 되어 있어야 함
배열, 이진 트리 사용하여 구현
시간 복잡도 O(log n) 로 빠름

 

이진 탐색 구현 - 배열

원하는 숫자를 찾기 방법은 다음과 같다.

---

1. 정렬된 배열에서 맨 앞을 left, 맨 뒤를 right, 가운데를 mid 로 설정
2. 찾는 숫자를 mid 값과 비교
   
   • mid 값이 더 크면 right = mid - 1
   • mid 값이 더 작으면 left = mid + 1
3. 새롭게 설정된 left 또는 right 값으로 mid 값 다시 설정
4. 이를 반복하여 mid 값과 찾는 숫자가 같으면 종료

---

배열을 사용하여 이진 탐색을 구현하면 선형 시간 O(n) 이 소요된다.

그래서 이를 해결하기 위해 이진 탐색 트리를 사용하여 구현한다.

 

그러나 실제 코딩 테스트에서는 배열을 사용하여 이진 탐색 구현하는 경우가 더 많다고 한다.

배열로 이진 탐색을 구현하는 방법은 아래 코드와 같다.

 

이진 탐색 구현 - 배열

실행 결과

실행 결과로 해당 배열에서 찾는 숫자의 인덱스 값을 얻게 된다.

 

이진 탐색 구현 - 이진 탐색 트리

이진 탐색 트리는 이존 이진 트리에서

왼쪽은 루트보다 작은 값들이 있고, 오른쪽은 루트보다 큰 값이 모여 있는 트리이다.

이진 탐색 트리

이진 탐색 트리는

값을 넣는 삽입(insert)하는 부분과 탐색(search) 하는 부분을 구현한다.

 

이진 탐색 구현 - 이진 탐색 트리

그래서 이진 탐색 트리에 값을 넣은 후, 찾는 값이 있는지 없는지 구할 수 있다.

 

---

 

해당 게시물은 프로그래머스 - 코딩테스트 광탈 방지 A to Z : JavaScript 강의를 참고하여 작성한 글입니다. (유료강의)

코딩테스트 광탈 방지 A to Z : JavaScript