[알고리즘] 순차 검색 (Sequential search) - 자바 Java

📍 검색이란?
- 저장되어 있는 자료 중에서 원하는 항목을 찾는 작업
- 목적하는 탐색 키(자료를 구별하여 인식할 수 있는 키)를 가진 항목을 찾는 것

[ 순차 검색이란? ]

: 원하는 키 값을 갖고 있는 요소를 만날 때까지 맨 앞에서부터 순서대로 요소를 검색하는 알고리즘 (선형 검색)
- 가장 간단하고 직관적이며, 배열/연결리스트 등 순차구조로 구현된 자료구조에서 검색시 유용
- 알고리즘이 단순하여 구현은 쉬우나 검색 대상수가 늘어날수록 시간이 급격히 증가하여 비효율적

[ 검색 과정 ]

- 첫 번째 원소부터 순서대로 검색 대상과 키 값이 같은 원소가 있는지 비교
- 키 값이 동일한 원소를 찾으면 해당 원소의 인덱스 반환
- 자료구조의 마지막까지 대상을 찾지 못하면 검색 실패
- 정렬되어 있는 배열의 경우, 순차적으로 검색하면서 키 값을 비교하고 원소의 키 값이 검색 대상의 키 값보다 크면 찾는 원소가 없다는 것이므로 더 이상 검색하지 않고 검색 종료(정렬되어 있지 않을 때보다 평균 비교 횟수가 반으로 감소)

[ 코드 예시 - 자바 Java ]

package search;

public class SequentialSearch {

  public static void main(String[] args) {
		
    int[] arr1 = {3, 5, 7, 9, 1};
    int[] arr2 = {1, 3, 5, 7, 9};
    
    System.out.println(sequentialSearch1(arr1, 2));
    System.out.println(sequentialSearch2(arr2, 5));
  }
	
  // 1. 정렬되어 있지 않은 배열 순차 검색.
  static int sequentialSearch1(int[] arr, int key) {
    int size = arr.length;
    
    for(int i = 0; i < size; i++) {
      if(arr[i] == key) return i;
    }
    // 못 찾을 경우.
    return -1;
  }
  
  // 2. 오름차순으로 정렬되어 있는 배열 순차 탐색.
  static int sequentialSearch2(int[] arr, int key) {
    int size = arr.length;
    
    for (int i = 0; i < size; i++) {
      if(arr[i] == key) return i;
      // arr[i] 값이 key보다 커지면 바로 종료.
      if(arr[i] > key) break;
    }
    
    // arr[i] 값이 key보다 커지지는 않았지만, 같은 값을 못 찾으면 종료.
    return -1;
  }
}