선형 검색 while, for, 보초법 사용하여 구현하기 (검색 알고리즘)

선형검색은 배열에서 검색하는 방법 중 가장 기본적인 알고리즘이다.

요소가 직선모양으로 늘어선 배열에서 

검색은 원하는 키 값을 갖는 요소를 만날때까지 맨앞부터 순서대로 요소를 검색한다.

이 검색을 선형검색(linear search) 또는 순차검색(sequential search) 이라고 한다.

1.  선형검색 알고리즘

package myTest1;
 
import java.util.Scanner;
 
public class SeqSearch {
 
    static int seqSearch(int[] array, int arrayLength, int key){
        int i=0;
        while(true){
            if(i==arrayLength) return-1;        // 검색 실패 -1을 반환
            if(array[i] == key) return i;        // 검색 성공(인덱스를 반환)
            i++;
        }
    }
 
    static int usingForSeqSearch(int[] array, int arrayLength, int key){
        for(int i=0; i<arrayLength; i++){
            if(array[i] == key){
                return i;
            }
        }
        return -1;
    }
 
    // 보초법
    static int seqSearchSen(int[] array, int arrayLength, int key){
        int i = 0;
        // arrayLength = 3, key = 2
        // array[0] = 1, array[1] = 2, array[2] = 3
        // array[3] = 2
        array[arrayLength] = key;    // 보초를 추가
        while(true){
            if(array[i] == key) break;
            i++;
        }
        // array[3] 에 있다면 못찾은 것 -1 return
        return i == arrayLength? -1 : i ;
    }    
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("배열길이: ");
        int arrayLength = scanner.nextInt();
        int[] array = new int[arrayLength+1];
        
        
        for(int i=0; i<arrayLength; i++){
            System.out.print("x[" + i + "] : ");
            array[i] = scanner.nextInt();
        }
        System.out.print("검색할 값: ");
        int key = scanner.nextInt();
        int idx1 = seqSearch(array, arrayLength, key);        // 배열 array에서 키 값이 key인 요소를 검색
        int idx2 = usingForSeqSearch(array, arrayLength, key);
        int idx3 = seqSearchSen(array, arrayLength, key);
        
        if(idx1 == -1){
            System.out.println("그 값의 요소가 없습니다.");
        }else{
            System.out.println(key+"은(는) x[" + idx1 + "]에 있습니다.");
        }
        
        if(idx2 == -1){
            System.out.println("그 값의 요소가 없습니다.");
        }else{
            System.out.println(key+"은(는) x[" + idx2 + "]에 있습니다.");
        }
 
        if(idx3 == -1){
            System.out.println("그 값의 요소가 없습니다.");
        }else{
            System.out.println(key+"은(는) x[" + idx3 + "]에 있습니다.");
        }
    }
}

결과

while문, for문, 보초법을 사용해 해당 배열에서의 키값을 찾아낸다.

보초법은 기존 배열의 길이를 +1 증가시켜

배열의 맨 마지막 길이의 요소에 찾을 키 값을 넣고

찾는 키값이 마지막에 찾게 될 경우 -1을 리턴한다.

소스코드 첨부

myTest1.zip