[Algorithm] Binary Search (재귀호출을 사용하여~)

1. 개념과 원리

배열에 있는 특정 숫자를 검색할려면 O(n)이 걸린다.

더 빠르게 못하나? 할수있다!

Binary Search를 사용해 할 수 있다.

단, 정렬이 되어 있는 경우에만 사용이 가능하다.

1. 중간값을 본다. 이 값이랑 찾고자 하는 값이랑 비교를 한다.

2. 내가 찾고자 하는 값은 왼쪽일까요 ? 오른쪽 일까요? 

3. 또 중간값을 ~ 반복해서 비교하여 날릴 구간을 정한다.

2. 시간복잡도

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

200개라고 가정. 

- 100개 - 50개 -25개 - 12개 or 13개 - 7개 - 4개 -2개 - 1개 

200개는 총 8번의 비교를 하게 된다. 

O(logN) 이다. 

의문점: 결국은 정렬을 해야 하니.. nlog(n) 이 아니냐 ?  맞음

이미 배열이 정렬되어 들어온다고 가정해봐요.. 이미 정렬된 경우의 문제는 반드시 Binary Search를 사용해야 하고,

반환형이 int임을 알 수 있다. 이것은 배열에서의 위치를 반환한다는 의미이다.

반드시 암기하자. 암기가 생명이라고 현직자분이 말씀하셨다.

return true 가 아니고, return s; 이고 return false 가 아니고, return -1 이다.  (수정) - 기저조건

<구현연습>

#include <stdio.h>

int binarySearch(int arr[], int start, int end, int target){

  // arr의 start부터 end까지의 값들 중에서 

  // value가 존재하면 그 위치를 반환하고, 

  // 그렇지 않으면 -1을 반환하는 함수

  // 탈출조건을 만들었다.

  if(start>end){

    return -1;

  }else if(start == end){

    if(arr[start] == target) return start;

    else return -1;

  }else{

    // 1 2 6 9 10 11 15 19 30 

    // target 9 라고 가정 

    int mid = (start+end) / 2;

    if(arr[mid] == target) return mid;

    else if(arr[mid]>value) return binarySearch(arr,start,mid-1,target);

    else if(arr[mid]<value) return binarySearch(arr,mid+1,end,target);

  }

}

int main() {

  //Please Enter Your Code Here

  int n,m;

  int arr[100];

  scanf("%d",&arr[i]);

  // arr은 반드시 정렬이 되어 있어야 함.

  for(int i=0; i<n; i++)

    scanf("%d",&arr[i]);

  

  scanf("%d",&m);

  int inx = binarySearch(arr,0,n-1,m);

  // -1이면 값을 못 찾았다 !! 

  // 만약에 찾았으면 배열의 위치를 반환 

  

  if(inx==-1){

    printf("없다");

  }else{

    printf("%d 번째의 배열에 니가 원하는 값이 있다.",inx);

  }

  return 0;

}