알고리즘 study -14-

<이진 탐색 Binary Search>

-> 정렬되어 있는 숫자들 중에서 특정 숫자를 찾는다

---

숫자를 절반씩 지워나가면서 찾는다

-> 숫자를 몇번 2로 나눠야 1이되냐 = O(logn)

---

숫자 찾기를 매우 많이 해야하는 경우에는 정렬을 한 뒤에 Binary Search를 하는 것이 좋다!

ex> 배열에 숫자가 1000개 인데, 숫자 찾기를 100,000 번 해야 한다면??

---

<이진 탐색 구현 - 1.재귀호출 사용 >

#include <stdio.h>

int binarySearch(int arr[], int start, int end, int value){
  //arr의 start 부터 end 까지 값들 중에서
  // value가 존재한다면 그 위치를 반환(인덱스)
  // 없다면 -1 반환하는 함수
  
  if(start>end){    // 1. 시작 인덱스가 더 크면 바로 -1 리턴!
    return -1;
  }
  else if(start == end){ // 2. 시작, 끝 인덱스 값 같은 경우!
    if(arr[start] == value)
      return start;
    else
      return -1;
  }
  else{  // 3. start~end 범위 내에 원소가 2개 이상인 경우!
    int mid = (start + end)/2;
    if(arr[mid] == value) return mid;
    else if(arr[mid] > value)
      return binarySearch(arr, start, mid-1, value);
    else
      return binarySearch(arr, mid+1, end, value);
  }
  
}

int main() {

  int n, m;
  int arr[100];
  
  scanf("%d", &n);
  
  // arr은 정렬이 되어 있어야 함
  for(int i = 0; i<n; i++)
    scanf("%d", &arr[i]);
  
  scanf("%d", &m); // 찾고자 하는 값
  
  int index = binarySearch(arr, 0, n-1, m);
  
  if(index == -1)
    printf("찾으려는 수가 없습니다\n");
  else
    printf("%d번째에 찾으려는 수가 있습니다\n", index+1);

  
  return 0;
}

---

<이진 탐색 구현 - 2.재귀호출 사용 X >

-> while 을 사용하여 구현 가능

---

start = 찾고자 하는 값보다 항상 작은 값을 가리킴
end = 찾고자 하는 값보다 항상 큰 값을 가리킴

재귀호출 사용x 이진탐색에서는 위 의미 정확히 숙지하기!!

---

#include <stdio.h>

int binarySearch(int arr[], int myStart, int myEnd, int value){
  // arr의 start 부터 end 까지 중에서 value 찾아서 위치 반환
  // 없다면 -1 반환
  
  int start, end;
  // start : value보다 항상 작은 값을 가리키는 인덱스
  // end : value보다 항상 큰 값을 가리키는 인덱스
  // 따라서 start 다음에 바로 end 있으면 찾으려는 값이 없다
  
  int mid;
  
  if(arr[myStart] > value) return -1;
  else if(arr[myStart] == value) return myStart;
  
  if(arr[myEnd] < value) return -1;
  else if(arr[myEnd] == value) return myEnd;  
  //  시작과 끝에 value가 있는 경우
  
  start = myStart;
  end = myEnd;
  
  while(start + 1 < end){  // start end 붙어 있으면 끝
    mid = (start + end)/2;
    
    if(arr[mid] == value) return mid;
    else if(arr[mid] > value) end = mid;
    else start = mid;
    
    // 재귀 방식과 다르게 start+1<end 조건이 있어서
    // mid 값이 그대로 start 혹은 end에 할당된다!
  }
  
  return -1; // while 문에서 못 찾는 경우
}

int main() {

  int n, m;
  scanf("%d", &n);
  
  int arr[100];
  for(int i = 0; i<n;i++){
    scanf("%d", &arr[i]);
  }
  
  scanf("%d", &m); // 찾고자 하는 값
  
  int index = binarySearch(arr, 0, n-1, m);
  
  printf("%d 번째에 %d이 있습니다", index+1, m);

  return 0;
}

---