[자바기초.022] 재귀 탐색&정렬(Recursive Searching and Sorting))

[자바기초.022] 재귀 탐색&정렬(Recursive Searching and Sorting)

 

[1] 재귀 이진 탐색(Recursive Binary Search)

1.이진 탐색(Binary Search)

• 선형 탐색(Linear search)은 배열이나 리스트에 저장된(in order) 데이터를 하나씩 비교하면서 천천히 원하는 데이터를 찾는 알고리즘 입니다. 
• 이진 탐색(Binary search)는 선형 탐색보다 더 빠르게 데이터를 찾는 방법으로서, 정렬된 데이터의 가장 가운데 위치한 것부터 데이터 크기를 비교하여, 비교대상의 절반을 버려가면서 원하는 데이터를 찾는 알고리즘 입니다.
• Binary search only works on sorted data.

<Linear Search 예제 코드>

for (int j = 0; j < elements.length; j++)
{
   if (elements[j] == target)
   {
       return j;
   }
}
return -1;

 

<Binary Search 예제 코드>

public class Main {
  public static int binarySearch(int[] elements, int target) {
      int left = 0;
      int right = elements.length - 1;
      while (left <= right) {
          int middle = (left + right) / 2;
          if (target < elements[middle]) {
              right = middle - 1;
          }
          else if (target > elements[middle]) {
              left = middle + 1;
          }
          else {
              return middle;
          }
      }
      return -1;
  }
  
  public static void main(String[] args) {
    int[] arr1 = {-20, 3, 15, 81, 432};
 
    int index = binarySearch(arr1, 81);
    System.out.println(index);
  }
}
 

 

 

2.재귀 이진 탐색(Recursive Binary Search)

• 아래 코드는 이진 탐색을 재귀(Recursive) 방식으로 다시 코딩한 예제 코드입니다.
• 이진 탐색은 그냥 반복문만으로 코딩하는 게 더 효율적이지만 재귀를 공부해보는 차원에서 코드를 봐주세요.

public class Main {
  public static int recursiveBinarySearch(
      int[] array, int start, int end, int target) {
      int middle = (start + end) / 2;
      // base case: check middle element
      if (target == array[middle])
      {
          return middle;
      }
      // base case: check if we've run out of elements
      if (end < start)
      {
          return -1; // not found
      }
      // recursive call: search start to middle
      if (target < array[middle])
      {
          return recursiveBinarySearch(array, start, middle - 1, target);
      }
      // recursive call: search middle to end
      if (target > array[middle])
      {
          return recursiveBinarySearch(array, middle + 1, end, target);
      }
      return -1;
  }
  
  public static void main(String[] args) {
    int[] array = {3, 7, 12, 19, 22, 25, 29, 30};
    int target = 25;
    int foundIndex = recursiveBinarySearch(array, 0, array.length - 1, target);
    System.out.println(target + " was found at index " + foundIndex);
  }
}
 

 

 

 

 

---