[이것이 코딩 테스트다 with Python]_26_이진탐색

220208 작성

<본 블로그는 『이것이 취업을 위한 코딩 테스트다』 의 youtube를 참고해서 공부하며 작성하였습니다>

https://www.youtube.com/watch?v=-Gx0T92-7h8&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=26 

 

 

 

 

 

 

1. 순차 탐색

: 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인

 

 

 

2. 이진 탐색

: 정렬되어 있는리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법

: 시작점, 끝점, 중간점을 이용하여 탐색 범위 설정

 

 

1) 이미 정렬된 데이터, 4를 찾아보자

2) 시작점 [0], 끝점 9, 중간점 [4](소수점 이하 제거)

3) 중간점 기준으로 왼쪽꺼만 살림

4) 다시 시작, 중간, 끝점 찾는다  0, 2, 4, 6

5) 2 를 기준으로 오른쪽꺼만 살림

6) 4, 6 끝

 

 

 

• python

  def binary_search(array, target, start, end) :
      if start > end :
          return None
      mid = (start + end) // 2
  
      if array[mid] == target :
          return mid
      # 왼쪽 살림
      elif array[mid] > target :
          return binary_search(array, target, start, mid-1)
      # 오른쪽 살림
      else :
          return binary_search(array, target, mid+1, end)
  
  n, target = list(map(int, input().split()))
  
  array = list(map(int, input().split()))
  
  result = binary_search(array, target, 0, n-1)
  
  if result == None :
      print("원소 없음")
  else :
      print(result+1)

   

• c++

#include <bits/stdc++.h>

using namespace std;

// 이진 탐색 소스코드 구현(반복문)
int binarySearch(vector<int>& arr, int target, int start, int end) {
    while (start <= end) {
        int mid = (start + end) / 2;
        // 찾은 경우 중간점 인덱스 반환
        if (arr[mid] == target) return mid;
        // 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
        else if (arr[mid] > target) end = mid - 1;
        // 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
        else start = mid + 1; 
    }
    return -1;
}

// N(가게의 부품 개수)와 M(손님이 확인 요청한 부품 개수)
int n, m;
// 가게에 있는 전체 부품 번호들
vector<int> arr;
// 손님이 확인 요청한 부품 번호들
vector<int> targets;

int main(void) {
    cin >> n;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        arr.push_back(x);
    }
    
    // 이진 탐색을 수행하기 위해 사전에 정렬 수행
    sort(arr.begin(), arr.end());
    
    cin >> m;
    for (int i = 0; i < m; i++) {
        int target;
        cin >> target;
        targets.push_back(target);
    }
    // 손님이 확인 요청한 부품 번호를 하나씩 확인
    for (int i = 0; i < m; i++) {
        // 해당 부품이 존재하는지 확인
        int result = binarySearch(arr, targets[i], 0, n - 1);
        if (result != -1) {
            cout << "yes" << ' ';
        }
        else {
            cout << "no" << ' ';
        }
    }
}

 

• java

import java.util.*;

public class Main {

    // 이진 탐색 소스코드 구현(재귀 함수)
    public static int binarySearch(int[] arr, int target, int start, int end) {
        if (start > end) return -1;
        int mid = (start + end) / 2;
        // 찾은 경우 중간점 인덱스 반환
        if (arr[mid] == target) return mid;
        // 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
        else if (arr[mid] > target) return binarySearch(arr, target, start, mid - 1);
        // 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
        else return binarySearch(arr, target, mid + 1, end);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        // 원소의 개수(n)와 찾고자 하는 값(target)을 입력받기 
        int n = sc.nextInt();
        int target = sc.nextInt();

        // 전체 원소 입력받기 
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

        // 이진 탐색 수행 결과 출력 
        int result = binarySearch(arr, target, 0, n - 1);
        if (result == -1) {
            System.out.println("원소가 존재하지 않습니다.");
        }
        else {
            System.out.println(result + 1);
        }
    }

}

 

 

 

 

 

3. 이진 탐색 시간 복잡도

: 단계마다 탐색 범위를 2로 나누는 것

: 연산횟수는 log2N에 비례

: 시간복잡도는 O(logN)

=> O(logN)

 

 

 

 

 

 

4. 파이썬 이진 탐색 라이브러리

- bisect_left(a, x) : 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 왼쪽 인덱스를 반환

- bisect_right(a, x) : 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 오른쪽 인덱스를 반환

from bisect import bisect_left, bisect_right

a = [1, 2, 4, 4, 8]
x = 4

print(bisect_left(a, x))
print(bisect_right(a, x))

 

 

+) 값이 특정 범위에 속하는 데이터 개수 구하기

from bisect import bisect_left, bisect_right

def count_by_range(a, left_value, right_value) :
    right_index = bisect_right(a, right_value)
    left_index = bisect_left(a, left_value)

    return right_index - left_index

a = [1, 2, 4, 4, 6, 6, 6, 7, 8]

# 4 몇개
print(count_by_range(a, 4, 4))
# [-1, 3] 범위 개수
print(count_by_range(a, -1, 3))