알고리즘 - 배열 검색

1. 선형 검색

• 무작위로 늘여 놓은 데이터 모임에서 아주 빠른 검색을 수행한다.
• 조건
  • 검색할 값을 발견하지 못하고 배열의 끝을 지나간 경우
  • 검색할 값과 같은 요소를 발견한 경우
• cost : n

public class Main {

    public static void main(String[] args) {
        int[] nums = {1,2,7,9,0};
        System.out.println(solution(nums, 7));
    }

    public static int solution(int[] nums, int key){
        int size = nums.length;

        for(int i = 0; i < size; i++){
            if(nums[i] == key){
                return i;
            }
        }

        return -1;
    }
}

• 보초법
  • 배열 마지막에 찾고자 하는 key를 삽입하여 조건 1이 성립하지 않도록한다.
  • 조건 1이 빠지고 조건 2만 만족하면 되므로 종료 판단을 2회에서 1회로 줄일 수 있다.

---

2. 이진 검색

• 일정한 규칙으로 늘어놓은 데이터 모임에서 아주 빠른 검색을 수행한다.
• 반으로 줄여나가면서 검색한다.
• 반을 기준으로 key가 반보다 작으면 반의 앞에서 다시 반으로 줄이면서 검색.
• 크면 반의 뒤에서 다시 반으로 줄이면서 검색한다.
• 조건
  • 검색 범위가 더 이상 없는 경우
  • 검색할 값과 같은 요소를 발견한 경우
• cost : log(n+1)

public class Main {

  public static void main(String[] args) {
    int[] nums = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20};
    System.out.println(solution(nums, 7));
  }

  public static int solution(int[] nums, int key) {
    int length = nums.length;

    // 검색 범위의 첫 인덱스
    int pl = 0;
    // 검색 범위의 끝 인덱스
    int pr = length - 1;

    do {
      // 중앙 인덱스
      int pc = (pl + pr) / 2;

      // 중앙 인덱스와 key가 같다면 끝
      if (nums[pc] == key) {
        return pc;
      }
      // key 보다 중앙 인덱스가 작다면 검색 범위를 뒤쪽 절반으로 좁힌다.
      else if (nums[pc] < key) {
        pl = pc + 1;
      }
      // key 보다 중앙 인덱스가 크다면 검색 범위를 앞쪽 절반으로 좁힌다.
      else {
        pr = pc - 1;
      }
    } while (pl <= pr);

    // 검색 실패
    return -1;
  }
}

• Java에서는 배열에서 이진검색 라이브러리를 지원한다.
  • Arrays.binarySearch 

public class Main {

  public static void main(String[] args) {
    int[] nums = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20};
    System.out.println(Arrays.binarySearch(nums, 7));
   }
 }

---

3. 해시법

• 추가, 삭제가 자주 일어나는 데이터 모임에서 아주 빠른 검색을 수행한다.
• 체인법 : 같은 해시 값의 데이터를 선형 리스트로 연결하는 방법.
• 오픈 주소법 : 데이터를 위한 해시 값이 충돌할 때 재해시하는 방법.