chpt7_binary_search_review.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "3be405b4",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n"
     ]
    }
   ],
   "source": [
    "# 이진 탐색 소스 코드\n",
    "\n",
    "def binary_search(array, target, start, end):\n",
    "    if start > end:\n",
    "        return None\n",
    "    mid = (start+end)//2\n",
    "    \n",
    "    if array[mid] == target:\n",
    "        return mid\n",
    "    elif array[mid] > target:\n",
    "        return binary_search(array, target, start, mid-1)\n",
    "    else:\n",
    "        return binary_search(array, target, mid+1, end)\n",
    "    \n",
    "\n",
    "n, target = map(int, input().split())\n",
    "\n",
    "\n",
    "print(binary_search(array, 7, 0, len(array)-1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "e534ba59",
   "metadata": {},
   "outputs": [],
   "source": [
    "# 반복문 이진탐색\n",
    "\n",
    "def bi_s(array, target, start, end):\n",
    "\n",
    "    \n",
    "    while start<=end:\n",
    "        mid = (start+end)//2\n",
    "        \n",
    "        if array[mid] == target:\n",
    "            return mid\n",
    "        elif array[mid] > target:\n",
    "            end = mid-1\n",
    "        else:\n",
    "            start = mid+1\n",
    "            \n",
    "    return None\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "3725189c",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5\n",
      "8 3 7 9 2\n",
      "3\n",
      "5 7 9\n",
      "no yes yes "
     ]
    }
   ],
   "source": [
    "# 7-2 / 실전 문제 / 부품 찾기\n",
    "\n",
    "n = int(input())\n",
    "\n",
    "array = list(map(int, input().split()))\n",
    "\n",
    "m = int(input())\n",
    "\n",
    "parts = list(map(int, input().split()))\n",
    "\n",
    "array.sort()\n",
    "\n",
    "def find(array, target, start, end):\n",
    "    if start > end:\n",
    "        return False\n",
    "    mid = (start+end)//2\n",
    "    if array[mid] == target:\n",
    "        return True\n",
    "    elif array[mid] > target:\n",
    "        return find(array, target, start, mid-1)\n",
    "    else:\n",
    "        return find(array, target, mid+1, end)\n",
    "    \n",
    "    return False\n",
    "\n",
    "for i in parts:\n",
    "    if find(array, i, 0, n-1):\n",
    "        print(\"yes\", end=' ')\n",
    "    else:\n",
    "        print(\"no\", end=' ')\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "9e8bf225",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4 6\n",
      "19 15 10 17\n",
      "15\n"
     ]
    }
   ],
   "source": [
    "# 7-3 / 실전 문제 / 떡볶이 떡 만들기 written by me\n",
    "\n",
    "n, m = map(int, input().split())\n",
    "\n",
    "arr = list(map(int, input().split()))\n",
    "\n",
    "pre = 0\n",
    "\n",
    "def remainCake(arr, h):\n",
    "    count = 0\n",
    "    for i in arr:\n",
    "        if h < i:\n",
    "            count+=(i-h)\n",
    "            \n",
    "    return count\n",
    "\n",
    "def bi_s(arr, ob, start, end):\n",
    "    global pre\n",
    "    if start > end:\n",
    "        return pre\n",
    "    mid = (start+end)//2\n",
    "    res = remainCake(arr, mid)\n",
    "    if res >= ob: # 절단기 높이를 더 높게!\n",
    "        pre = mid\n",
    "        bi_s(arr, ob, mid+1, end)\n",
    "        \n",
    "    else: # 절단기 높이를 더 낮게\n",
    "        if mid < pre:\n",
    "            return pre\n",
    "        else:\n",
    "            bi_s(arr, ob, start, mid-1)\n",
    "\n",
    "bi_s(arr, m, min(arr), max(arr))\n",
    "print(pre)\n",
    "            \n",
    "            \n",
    "    \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "8afec06a",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4 6\n",
      "19 15 10 17\n",
      "15\n"
     ]
    }
   ],
   "source": [
    "# 7-3 written by author\n",
    "\n",
    "n, m = map(int, input().split())\n",
    "\n",
    "array = list(map(int, input().split()))\n",
    "\n",
    "start = 0\n",
    "\n",
    "end = max(array)\n",
    "\n",
    "result = 0\n",
    "\n",
    "while start <= end:\n",
    "    total = 0\n",
    "    mid = (start+end)//2\n",
    "    for x in array:\n",
    "        if x > mid:\n",
    "            total += x-mid\n",
    "    \n",
    "    if total < m:\n",
    "        end = mid - 1\n",
    "    else:\n",
    "        result = mid\n",
    "        start = mid+1\n",
    "        \n",
    "print(result)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}