[알고리즘 트레이닝 1일차] binary search Algorithm (이진검색)

binary search Algorithm. (이진검색)

정렬된 리스트를 검색하여 값을 찾는 알고리즘 이며, 반복하는 횟수가 탐색시간이 된다.

예를들어 

라 가정할때 

횟수 만큼 조회하게 되며 조회 시 마다 검색할 

리스트 길이가 로 줄게된다. 따라서 시간복잡도는  이 된다.

일반적으로 DB의 index검색에 많이 쓰이지만,  DB에 insert, update등의 입력, 수정이

빈번하게 일어날 경우 index는 좋지않다. 이유는 위에서 설명했듯이 검색하는 키값이 정렬되어야

하기 때문에 입력,수정이 발생할 경우 매번 재정렬이 필요하다. 결론적으로 조회 위주의 테이블 

컬럼에 적절히 사용하면 좋다.

c++을 이용하여 예제코드를 살펴본다.

예제 코드는 아래와 같다.

#include <iostream>
#define ARRAY_SIZE 1000
int bin_search(int *search, int value);
int count=0, start=0, end=0;
int main()
{
     int search[ARRAY_SIZE] = {};
     for(int i=0; i < ARRAY_SIZE; i++){
       search[i] = i+1;
     }
     int num=0;
     end=ARRAY_SIZE;
     std::cout << "Input Find Value : ";
     std::cin >> num;
     count = bin_search(search, num);
     std::cout << "Search Count : " << count << std::endl;
     return 0;
}

int bin_search(int *search, int value)
{
  count++;
  int index = start + ((end-start)/2);
  std::cout << "### Searching Value : " << search[index] << std::endl;
  if( value == search[index] )
    std::cout << "Find Value : " << value << std::endl;
  else{
    if((end - start) == 1){
      std::cout << " Not Found Value : " << value << std::endl;
      return count;
    }
    if(value > search[index]){
      start = index;
      bin_search(search, value);
    }else if(value < search[index]){
      end = index;
      bin_search(search, value);
    }
  }
  return count;
}

이진검색은 분할정복 ( Divide And Conquer ) 알고리즘 중에 한가지이다. 

기본적으로 많이 쓰이는 알고리즘이기 때문에 필수적으로 알아 두는것이 좋다. 

이상으로 이진검색 알고리즘에 대한 소개를 마친다.

.by rocksea