사용자 도구

사이트 도구


알고리즘:binary_search
| binary search
#define MAXN ((int)1e5 + 10) // 100,000 + 10
int data[MAXN];
 
int binarySearch(int s, int e) {
  int sol = 0; // 못 찾았을 때 필요한 값을 넣는다.
  while(s <= e) {
    int m = (s + e) / 2;
    if(data[m]과 비교할 조건) {
      // 찾았을 때
      sol = m;
      s = m + 1;  // 조건에 따라 m + 1이냐, m - 1이냐를 결정해야 함
 
    } else {
      e = m - 1;  // 위에 정한 것과 반대. 변수는 s가 아닌 e임을 주의할 것
    }
  }
 
  return sol;
}

int main(void) {
 
  input(); // data 배열에 값을 넣는 함수가 있다고 가정
  int sol = binarySearch(0, N - 1);
  if(sol == 0) {
    // 못 찾은 경우
  }  else {
    // 찾은 경우로, sol을 인덱스로 사용
  }
 
  return 0;
}
알고리즘/binary_search.txt · 마지막으로 수정됨: 2019/10/17 09:31 저자 trsprs