binarySearch.md

이진탐색, 이분탐색 (Binary Search)

• 이진 탐색은 데이터가 정렬되어 있는 배열에서 특정한 값을 찾아내는 알고리즘
• 배열의 중간 값을 이용해 찾고자하는 값 x와 비교함
  • x가 중간 값보다 작으면 중간 값을 기준으로 좌측의 데이터를 대상으로,
  • x가 중간 값보다 크면 중간 값을 기준으로 우측의 배열을 대상으로 다시 탐색함
  • 해당 값을 찾을 때까지 이 과정을 반복
• 시간복잡도: O(log n)

풀이방법

1. 우선 배열을 정렬한 후 풀어야 함
2. 찾고자하는 target 변수가 있어야 함
3. 2개의 포인터 변수가 필요함
   • lt: 왼쪽
   • rt: 오른쪽
4. 배열의 중간값에 대한 정보를 저장할 변수가 필요함
   • mid: parseInt((lt+rt)/2)
5. mid를 구하고 target과 array[mid]의 값 비교하여 검색 범위 줄이기
   1. target = array[mid] : 맞은 경우 답을 바로 찾아냄
   2. target > array[mid] : 찾고자하는 값이 오른쪽에 있으므로 lt = mid + 1;로 바꿔주어야 함
   3. target < array[mid] : 찾고자하는 값이 왼쪽이 있으므로 rt = mid - 1;로 바꿔주어야 함
6. 위의 과정을 lt >= rt일 때까지 찾기
   • 즉, 항상 lt <= rt인 경우에만 반복 (while문 이용하기)

결정 알고리즘

• 결정 알고리즘은 기본 베이스가 이분탐색임