[알고리즘] 1-3. 재귀함수 활용

암시적 매개변수를 명시적 매개변수로

-> 

//1. 순차 탐색

int search(int [] data, int n, int target) {
 for (int i=0; i<n; i++)
  if (data[i] == target)
   return i;
  return -1;
}

//data[0]과 data[n-1]사이의 target 검색
//시작 인덱스인 0을 생략하는 암시적 매개변수

//데이터 정렬이 되어 있지 않을 경우 : 순차 탐색
//데이터 정렬이 되어 있을 경우 : 이진 검색

 

//2. 매개변수 명시화 (1) : 순차 탐색

int search (int [] data, int begin, int end, int target) {
 if (begin > end)
  return -1;
 else if (target == data[begin])
  return begin;
 else
  return search(data, begin + 1, end, target);
}

//data[begin]에서 data[end]까지 target을 검색 : 검색구간 시작점을 명시적
// search(data, 0, n-1, target)이면 1.과 같은 함수


//end 생략시

int search (int [] data, int begin, int target) {
 if (begin > data.length-1)
  return -1;
 else if (target == data[begin])
  return begin;
 else
  return search(data, begin + 1, target);
}


// target을 end값과 비교시 [뒤에서 부터 비교]

int search(int [] data, int begin, int end, int target) {
 if (begin > end)
  return -1;
 else if (target == data[end])
  return end;
 else
  return search(data, begin, end-1, target);
 }
 
 
 //중간에서 부터 검색
 int search(int [] data, int begin, int end, int target) {
  if (begin>end) {
   return -1;
  else {
   int middle = (begin + end) /2;
   if (data[middle] == target)
    return middle;
   int index = search(data, begin, middle - 1, target);
   if (index != -1)
    return index;
   else
    return search(data, middle+1, end, target);
   }
  }

 

 

//3. 매개변수 명시화 (2) : 최대값 찾기

int findMax (int [] data, int begin, int end) { 
 if (begin == end)
  return datab[begin];
 else
  return Math.max(data[begin], findmax(data, begin+1, end));
}


//처음부터 값과 중간에서부터의 값을 비교
int findMax(int [] data, int begin, int end) {
 if (begin==end)
  return data[begin];
 else {
  int middle = (begin+end) /2;
  int max1 = findMax(data, begin, middle);
  int max2 = findMax(data, middle+1, end);
  return Math.max(max1, max2);
}

 

//4. 이진 검색 [Binary Search]
public static int binarySearch(String[] items, String target, int begin, int end) {
 if (begin>end)
  return -1;
 else {
  int middle = (begin+end) /2;
  int compResult = target.compareTo(items[middle]);
  if (compResult == 0)
   return middle;
  else if (compResult<0)
   return binarySearch(items, target, begin, middle-1);
  else
   return binarySearch(items, target, middle+1, end);
 }
}