[알고리즘] Binary Search

Emily·2020년 10월 26일

알고리즘

목록 보기

6/8

Abstract

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

Process(Ascending)

정렬을 한다. 오름차순으로 정렬한다고 가정한다.

mid 값을 정한다. mid = (left+right)/2

mid 와 찾고자 하는 값을 비교한다.

구할 값이 mid보다 Index가 높으면 left = mid + 1
구할 값이 mid보다 Index가 낮으면 right = mid - 1

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;
}