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

* while 문을 사용하여 구현할 수 있다.

* 생각보다 어렵다.

구현하는 과정이 생각보다 복잡하다. 하지만 각각의 변수가 무슨 역할을 하는지 말로 명확히 정의를 한다면 구현하는 데 도움이 될 수 있다.

<코드>

// 비재귀호출

#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보다 항상 큰 값을 가리킴.

  int mid;

  // 범위를 초과하는 value의 값일 경우 없다고 말해야 함.

  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;

 

  

  start = myStart;

  end = myEnd;

  // value : 29

  // 1 4 7 10 19 22 24 27 39

  // s                            e 

  //              s               e 

  //                      s       e 

  //                          s   e

  while( start+1 < end ){

    mid = start + end / 2;

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

    else if(arr[mid] > value) end = mid;

    else start = mid;

  }

  // while 문을 빠져나오면 인덱스 start와 end가 start+1 == end 관계일때 이다.

  return -1;

}

int main() {

  //Please Enter Your Code Here

  int n,m;

  int arr[100];

  

  scanf("%d",&n);

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

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

  

  scanf("%d",&m);

  

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

  if(inx == -1){

    printf("없다");

  }else{

    printf("%d 번째의 배열에 있네요",inx);

  }

  return 0;

}