[Java] 자료구조 - 선형 탐색과 이진 탐색

선형 탐색(Linear Search)

• 데이터를 순차적으로 탐색하여 원하는 요소를 찾는 방법.
• indexOf, contains, remove 메서드 등에서 이미 구현되어 있다.
• 동일관계를 확인할 수 있어야 하므로 객체는 equals 가 제공될 필요가 있다.

// O(n)
int search(int[] nums, int s) {
  for(int n : nums) {
    if(n == s) return n;
  }
  throw new Exception("Not Found");
}

이진 탐색(Binary Search)

• 중간 값을 선택하여 데이터의 범위를 좁혀가며 탐색하는 방법.
• 자바에서 Collection.binarySearch 메서드로 제공되고 있다.
• 대소관계를 비교하여 범위를 줄여나가는 방식이기 때문에 Comaparable 가 구현되어 있어야 하고, 순서대로 정렬되어 있어야 한다.

// O(logn)
int search(int[] nums, int s) throws Exception {
  int start = 0;
  int end = nums.length;

  while (start < end) {
    int mid = (end - start) / 2 + start;

    int d = nums[mid];
    if (d == s) return d;

    if (s < d) end = mid;
    else start = mid + 1;
  }

  throw new Exception("Not Found");
}