[알고리즘] Binary Search

Abstract

• 탐색 범위를 두 부분으로 분할하면서 찾는 방식.
• 처음부터 끝까지 돌면서 탐색하는 것보다 훨씬 빠르다.

Process(Ascending)

1. 정렬을 한다. 오름차순으로 정렬한다고 가정한다.
2. mid 값을 정한다. mid = (left+right)/2
3. mid 와 찾고자 하는 값을 비교한다.
4. 구할 값이 mid보다 Index가 높으면 left = mid + 1
   구할 값이 mid보다 Index가 낮으면 right = mid - 1
5. left가 right보다 커질 때 까지 반복한다.

C++ Code(Ascending)

int binarySearch(vector<int> arr, int target){
  int low = 0;
  int high = arr[arr.size()-1];

  while(low <= high){
    int mid = (low+high)/2;

    if(arr[mid] == target)
      return mid;

    if(arr[mid] > target)
      high = mid - 1;
    else 
      low = mid + 1;
  }
  return high;
}

GIF로 이해하는 Binary Search

시간복잡도

O(log₂n)

공간복잡도

O(n)

참고 사이트

Binary Search 설명
Binary Search Code
Binary Search Image