[알고리즘] 이분 탐색 Binary Search

    탐색 범위를 두 부분으로 분할하면서 찾는 방식

1. 정렬
2. low: 최소값의 인덱스, high: 최고값 인덱스, mid: 중간값 인덱스
3. mid와 내가 구하고자 하는 값과 비교
4. 구할 값이 mid보다 클 때: low = mid+1
   구할 값이 mid보다 작을 때: high = mid - 1
5. low > high 때 까지 반복

• 코드

#include <iostream>

using namespace std;

int main() {
   int arr[501];
   for(int i=1;i<501;i++) {
      arr[i]=i;
   }

   int target = 62; // 타겟 값
   
   // 이분 탐색 수행
   int low = 1, high = 500; // low, high 초기화
   while(low<=high) {
      int mid = (low+high)/2
      if(mid==target) {
         cout<<"탐색 완료"<<endl;
         break;
      } else if(mid>target) {
         high = mid-1;
      } else {
         low = mid+1;
      }
   }
   return 0;
}

• 시간복잡도: O(logn)
  크기가 n인 배열을 계속해서 절반으로 나누기 때문

참고링크