참고 사이트 :

[JS] 이진 탐색(이분 탐색)

이진 탐색 알고리즘(Binary Search Algorithm)이라고 한다.

특징은 이미 정렬되어 있는 배열에서 탐색 범위를 두 부분 리스트로 나눠 절반씩 좁혀가 필요한 부분에서만 탐색하도록 제한하여 원하는 값을 찾는 알고리즘이라고한다.

위 사이트에서 예시를 들어주는데 1~10 까지의 배열에서 3을 찾을 때

찾는 배열의 중간인 5를 기주능로 대소를 비교하고 3은 5보다 작기 때문에 두 부분 나눈 리스트에서 5이상은 탐색범위에서 제외시키고 5 이하의 부분에서 다시 탐색하게 되는 방식이다.

조건

• 정렬되어 있는 배열이 필요로 한다.
• left, right, mid의 변수가 필요하다.
  • left : 왼쪽의 끝 인덱스를 뜻함.
  • right : 오른쪽의 끝 인덱스를 뜻함.
  • left와 right의 사이는 탐색범위가 됨.
  • mid : left와 right 범위의 중간점이며 탐색하는 범위에서의 중간
    • 중간점은 (left + right) / 2 란 공식

시간 복잡도

O(logN)이며 단순히 매번 절반의 탐색할 데이터를 제외시킨다 생각하면 될 듯하다.

참고 : 전체 탐색은 O(N)이다.

진행과정

탐색범위의 중간 인덱스를 지정하고 ***찾고자 하는 값(target)***과 현재 중간 값을 비교함.

이 때 target 값과 중 값의 비교 값에 따른 조건을 걸어줌