c++/ 자료구조&알고리즘 개념 복습하기 - 18 / 이분탐색, Parametric Search

한창희·2022년 6월 5일

c++ 자료구조/알고리즘 개념 복습

목록 보기

18/23

< 이분탐색 >

정렬되어 있는 배열에서 특정 데이터를 찾기 위해 모든 데이터를 순차적으로 확인하는 대신 탐색 범위를 절반으로 줄여가며 찾는 탐색 방법
O(logN) 시간복잡도
이분탐색을 활용해 문제를 푸는 경우 탐색 종료 조건을 상황에 맞게 잘 설정하는 것이 중요하다!!

<이진 탐색 구현 - 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;
}

< STL binary_search >

O(logn)에 찾으려는 원소가 들어있는지 bool 형태로 반환
단, 정렬이 된 상태에서 사용 가능!!!

#include<iostream>
#include <vector>
#include <algorithm>

using namespace std;


int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	vector<int> V;

	V.push_back(2);
	V.push_back(17);
	V.push_back(16);
	V.push_back(21);
	V.push_back(5);
	V.push_back(10);
	V.push_back(3);

	sort(V.begin(), V.end());

	cout << binary_search(V.begin(), V.end(), 16) << "\n";
	cout << binary_search(V.begin(), V.end(), 100) << "\n";

	// 배열의 경우  arr, arr + n , number  의 형태로 사용 가능!!

	return 0;
}