1. 선형 검색

---

• '검색'대신 '탐색' 이라는 표현도 사용한다.
• '선형 검색(linear search)'대신 '순차 검색(sequential search)'라는 표현도 사용한다.

특징

• 배열에서 특정 요소를 검색할 때 사용되는 기본적인 알고리즘이다.
• 배열의 처음부터 끝까지 순차적으로 스캔하여, 원하는 값을 찾는다.

구현하기

알고리즘 종료 조건

1. 찾으려는 key값을 찾을 때.
2. 배열의 완전 탐색이 끝날 때.

public static int linear(List<Integer> arr, int key) {
	 // 리스트의 사이즈가 0이면 바로 -1 리턴.
     if (arr.size() == 0) {
	    return -1;
	}
	
    for (int i = 0; i < arr.size(); i++) {
        if (arr.get(i) == key) {
            return i;
        }
    }

    return -1;
}

책에서는 List가 아니라 기본배열을 사용하고, 보초법이라는 방법을 이용해서 루프가 끝나는 조건을 줄였는데, List를 사용하여 좀 더 간단한 소스 코드로 만들어보았다.

2. 이진 검색

---

특징

• 오른차순 or 내림차순으로 정렬이 된 배열 또는 트리에서 사용하는 검색 알고리즘이다.
• 배열에서 사용할 때는 배열이 정렬되어 있을 때만 사용할 수 있다.

구현하기 - 배열

탐색 영역의 중앙을 key값과 비교하고, 결과에 따라 아래 3가지중 하나를 시행한다.

• 비교하는 값(탐색 영역의 중앙값): x, 탐색영역의 왼쪽: left, 탐색영역의 오른쪽: right

  비교 결과	실행
  같음	루프를 종료하고 결과를 리턴함.
  key가 더 큼	x+1부터 right까지 다시 탐색.
  key가 더 작음	left부터 x-1까지 다시 탐색.

알고리즘 종료 조건

1. x와 key가 같음.
2. 더 이상 검색할 대상이 없음.

public static int binArr(List<Integer> arr, int key) {
    // 리스트의 사이즈가 0이면 바로 -1 리턴.
    if (arr.size() == 0) {
        return -1;
    }

    int left = 0;
    int right = arr.size() - 1;

    while (true) {
        int x = (right + left) / 2;
        // 값 비교
        int crtNum = arr.get(x);

        // 결과 처리
        if (crtNum == key) {
            return x;
        }

        if (crtNum > key) {
            right = x - 1;

        }else {  // crtNUm < key
            left = x + 1;
        }

        // 더 이상 탐색할 범위가 없으면 -1 리턴.
        if (left > right) {
            return -1;
        }
    }
}

Arrays.binarySearch

java에서는 java.util.Arrays 클래스에서 binarySearch 메서드를 통해 이진 검색을 따로 구현할 필요 없이 사용할 수 있다.