별의 공부 블로그 🧑🏻‍💻

🗒️ 이진 탐색 (2)

728x90
  1. 2021.05.29 [C++] 선형 탐색(Linear Search), 이진 탐색(Binary Search)

    선형 탐색(Linear Search), 이진 탐색(Binary Search) 선형 탐색(Linear Search) 시퀀스 전체 원소를 방문하면서 해당 원소가 N과 같은지 확인 다음과 같은 코드로 구현할 수 있음. bool linear_search(int N, std::vector& sequence) { for (auto i : sequence) { if (i == N) { return true; // 찾음! } } return false; } 장점 입력 시퀀스의 정렬 여부와 상관없이 항상 잘 동작함. 단점 효율적이지 않음. 주어진 배열이 정렬되어 있다는 점을 전혀 이용하지 못함. 시간 복잡도 : O(N) 이진 탐색(Binary Search) 주어진 시퀀스가 정렬되어 있다는 사실을 이용하여 검색하는 방법 ..

  2. 2017.06.21 [C] 탐색(Search)

    탐색(Search) [탐색이란?] - 탐색(search)은 컴퓨터가 가장 많이 하는 작업 중의 하나임. - 탐색은 컴퓨터 프로그램에서 가장 많이 사용하는 작업임과 동시에 많은 시간이 요구되므로 탐색을 효율적으로 수행하는 것은 매우 중요함. - 탐색은 기본적으로 여러 개의 자료 중에서 원하는 자료를 찾는 작업. - 탐색을 위하여 사용되는 자료 구조는 배열, 연결 리스트, 트리, 그래프 등 매우 다양할 수 있음. - 탐색 중에서 가장 기초적인 방법은 배열을 사용하여 자료를 저장하고 찾는 것. - 그러나 탐색 성능을 향상하고자 한다면 이진 탐색 트리와 같은 더욱 진보된 방법으로 자료를 저장하고 탐색해야 함. - 탐색의 단위는 항목이며, 항목은 간단하게 숫자일 수도 있고, 아니면 구조체가 될 수도 있음. - 항..

728x90
📖 Contents 📖

티스토리툴바