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

binary search Algorithm. (이진검색) 정렬된 리스트를 검색하여 값을 찾는 알고리즘 이며, 반복하는 횟수가 탐색시간이 된다. 예를들어 라 가정할때 횟수 만큼 조회하게 되며 조회 시 마다 검색할 리스트 길이가 로 줄게된다. 따라서 시간복잡도는 이 된다. 일반적으로 DB의 index검색에 많이 쓰이지만, DB에 insert, update등의 입력, 수정이 빈번하게 일어날 경우 index는 좋지않다. 이유는 위에서 설명했듯이 검색하는 키값이 정렬되어야 하기 때문에 입력,수정이 발생할 경우 매번 재정렬이 필요하다. 결론적으로 조회 위주의 테이블 컬럼에 적절히 사용하면 좋다. c++을 이용하여 예제코드를 살펴본다. 예제 코드는 아래와 같다. #include #define ARRAY_SIZE 10..
Developer 2014. 8. 13. 20:51
1