개념

<aside> 💡 이미 데이터가 정렬이 되어있는 상황에서 범위를 반씩 좁혀가며 빠르게 탐색하는 알고리즘이다.

</aside>

탐색 방법

<aside> 💡 "이분 탐색을 하는 방법은 left , right , mid 값으로 탐색하는 것이다. mid의 값은 (left + right)/2 으로 잡아주고 검색하고자 하는 값과 mid 값을 비교한다."

</aside>

1. 이분 탐색을 하고자 할 때 이미 정렬이 되어있어야 한다.
2. left, right로 mid값을 잡는다.
3. mid 값과 구하고자 하는 값을 비교한다.
4. 비교할시 mid 값보다 구하고자 하는 값이 높으면 left를 mid+1로 만들어주고 낮으면 right를 mid-1로 만든다.
5. left > right 가 될때까지 반복해서 구하고자 하는 값을 찾는다.

특징

1. 맨 처음에 데이터의 중간위치부터 출발
2. 시간 복잡도 O(logN) : 한번 탐색할 때 반씩 범위를 줄여나갈수 있다는 점에서 실제로 탐색속도가 매우 빠르다는 장점이 있음
3. 재귀함수를 이용하면 깔끔한 코드 작성이 가능
4. AVL 트리, B트리, 분할 정복 등에서 넓게 적용

c++

#include <iostream>
using namespace std;

int main()
{
   // 1~500까지의 배열 형성
   int arr[501];
   for(int i=1;i<501;i++)
      arr[i]=i;

   int target = 62; // 타겟 값
   // 이분 탐색 수행 (index 값)
   int left = 1, right = 500; // left, right 초기화
   while(left<=right)
   {
      int mid = (left+right)/2 // mid 갱신
      // 타겟 값 찾음
      if(mid==target)
      {
         cout<<"Searching Complete!"<<'\\n';
         break;
      }
      else if(mid>target)
      {
         right = mid-1;
      }
      else
      {
         left = mid+1;
      }
   }
   return 0;
}