[CS][알고리즘] 검색 알고리즘

순차 검색(Sequential Search)

• 선형검색이라고도 한다.
• 배열 처음부터 끝까지 차례대로 비교하여 원하는 데이터를 찾는 알고리즘
• 장점 : 검색 방법 중 가장 단순, 정렬되지 않은 리스트에서도 사용 가능

• 단점 : 검색할 리스트의 길이가 길면 비효율적

    String[] address = {"서울", "경기", "인천", "강원", "충청", "경상", "제주", "전라"};
  

  • 위의 배열 address에서 “제주” 데이터를 찾기 위해서는 0번 인덱스부터 6번 인덱스까지 모두 확인해야 한다.

복잡도

• O(n) : 선형 복잡도
• 입력 자료를 차례로 하나씩 모두 처리
• 수행 시간이 자료 크기와 정비례

이진 검색(Binary Search)

• 정렬되어 있는 리스트 에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 알고리즘
• 탐색 효율이 좋고 탐색 시간이 적게 소요
• 이진 탐색 가운데 레코드 번호
  • M 남은 범위 내에서 가운데 레코드 번호 = [ F 남은 범위 내에서 첫 번째 레코드 번호 + L 남은 범위 내에서 마지막 레코드 번호 / 2] (소수점일 경우 버림처리)

    int[] numArray = {1 , 6 , 12 , 17, 18, 50, 51};
  

  • numArray 에서 50찾기
    1. 1+7/2=4 이므로 4번째 값 확인 » 17
    2. 50은 17보다 크므로 5+7/2=6, 6번째 값 확인 » 50
    3. 원하는 값을 찾았으므로 이진 검색 종료

복잡도

• O(log₂n) : 로그형 복잡도
• 문제를 해결하기 위한 단계의 수가 log₂n번만큼의 수행 시간을 가짐