JavaAlgorithm03

검색

03-1 검색 알고리즘

검색과 키

• 주목하는 항목 : 키
• 키는 데이터의 일부
• 검색 조건
  • 키 값과 일치하도록 지정
  • 키 값의 구간을 지정
  • 키 값과 비슷하도록 지정

배열에서 검색하기

• 사용 알고리즘
  • 1. 선형검색 : 무작위로 늘어놓은 데이터 모임에서 검색을 수행한다.
    2. 이진 검색 : 일정한 규칙으로 늘어놓은 데이터 모임에서 아주 빠른 검색을 수행한다.
    3. 해시법 : 추가, 삭제가 자주 일어나는 데이터 모임에서 아주 빠른 검색을 수행한다.
• 검색에 사용할 알고리즘은 계산 시간이 짧은 것을 선택하면 된다.
• 데이터의 추가, 삭제 등을 자주하는 경우라면 검색 이외의 작업에 소요되는 비용을 종합적으로 평가하여 알고리즘을 선택한다.

03-2 선형 검색

• 배열에서 검색하는 방법 가운데 가장 기본적인 알고리즘.

선형 검색

• 요소가 직선 모양으로 늘어선 배열에서의 검색은 원하는 키 값을 갖는 요소를 만날 때까지 맨앞부터 순서대로 요소를 검색한다.
  • 이것이 선형 검색 또는 순차 검색이라는 알고리즘이다.
• 값이 key인 요소가 여러개 존재할 경우 반환값은 검색 과정에서 처음 발견한 요소의 인덱스가 된다.
• 값이 key인 요소가 존재하지 않으면 -1을 반환한다.

보초법

• 선형 검색은 반복할 때마다

  • 종료조건

    • 1. 검색할 값을 발견하지 못하고 배열의 끝을 지나간 경우

      2. 검색할 값과 같은 요소를 발견한 경우

• 를 모두 판단한다.

• 종료 조건을 검사하는 비용은 무시할 수 없다.

  • 이 비용을 반으로 줄이는 방법이 보초법이다.

03-3 이진 검색

​