이진 탐색.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-09-07T14:42:08.371466Z",
     "start_time": "2021-09-07T14:42:01.727620Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4 6\n",
      "19 15 10 17\n"
     ]
    }
   ],
   "source": [
    "N, M = map(int, input().split())\n",
    "tteok = list(map(int, input().split()))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-09-07T15:10:19.678687Z",
     "start_time": "2021-09-07T15:10:19.665663Z"
    }
   },
   "outputs": [],
   "source": [
    "def count_rest_tteok(length, tteok_list):\n",
    "    rest = 0 \n",
    "    for x in tteok_list:\n",
    "        diff = x - length\n",
    "        if diff > 0:\n",
    "            rest += diff\n",
    "        else:\n",
    "            pass\n",
    "    return rest  \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-09-07T15:10:28.138463Z",
     "start_time": "2021-09-07T15:10:28.116466Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "count_rest_tteok(17, tteok)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-09-07T15:13:15.423270Z",
     "start_time": "2021-09-07T15:13:15.413268Z"
    }
   },
   "outputs": [],
   "source": [
    "def binary_search(target, tteok_list, start, end):\n",
    "    while start <= end:\n",
    "        mid = (start+end) // 2\n",
    "        cutted_value = count_rest_tteok(mid, tteok_list)\n",
    "        best_tmp = 0\n",
    "        if cutted_value == target:\n",
    "            return mid \n",
    "        elif cutted_value > target:\n",
    "            start = mid+1\n",
    "            best_tmp = mid\n",
    "        else:\n",
    "            end = mid-1\n",
    "            \n",
    "    return best_tmp            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-09-07T15:15:00.514298Z",
     "start_time": "2021-09-07T15:15:00.493294Z"
    }
   },
   "outputs": [],
   "source": [
    "result = binary_search(M, tteok, 1, max(tteok))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-09-07T15:15:02.156807Z",
     "start_time": "2021-09-07T15:15:02.145806Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "15"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "result"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 정렬된 배열에서 특정 수의 개수 구하기 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-09-08T11:38:27.277315Z",
     "start_time": "2021-09-08T11:38:14.888268Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "7 4\n",
      "1 1 2 2 2 2 3\n"
     ]
    }
   ],
   "source": [
    "N, x = map(int, input().split())\n",
    "array = list(map(int, input().split()))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-09-08T11:38:29.938979Z",
     "start_time": "2021-09-08T11:38:29.927014Z"
    }
   },
   "outputs": [],
   "source": [
    "start=0\n",
    "end = len(array)-1\n",
    "best_left = 0\n",
    "while start <= end:\n",
    "    mid = (start+end)//2\n",
    "    if array[mid] > x:\n",
    "        end = mid-1\n",
    "    elif array[mid] < x:\n",
    "        start = mid+1\n",
    "    else:\n",
    "        best_left = mid\n",
    "        end = mid-1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-09-08T11:38:29.953975Z",
     "start_time": "2021-09-08T11:38:29.944000Z"
    }
   },
   "outputs": [],
   "source": [
    "start=0\n",
    "end = len(array)-1\n",
    "best_right = 0\n",
    "while start <= end:\n",
    "    mid = (start+end)//2\n",
    "    if array[mid] > x:\n",
    "        end = mid-1\n",
    "    elif array[mid] < x:\n",
    "        start = mid+1\n",
    "    else:\n",
    "        best_right = mid\n",
    "        start = mid+1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-09-08T11:41:55.131205Z",
     "start_time": "2021-09-08T11:41:55.111208Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "-1\n"
     ]
    }
   ],
   "source": [
    "if best_left ==0:\n",
    "    print(-1)\n",
    "else:\n",
    "    print(best_right+1-best_left)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-09-08T11:38:29.984046Z",
     "start_time": "2021-09-08T11:38:29.958980Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "best_left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-09-08T11:38:29.998977Z",
     "start_time": "2021-09-08T11:38:29.988977Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "best_right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-09-08T11:38:30.013992Z",
     "start_time": "2021-09-08T11:38:30.002982Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n"
     ]
    }
   ],
   "source": [
    "print(best_right+1-(best_left))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.7.3"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  },
  "varInspector": {
   "cols": {
    "lenName": 16,
    "lenType": 16,
    "lenVar": 40
   },
   "kernels_config": {
    "python": {
     "delete_cmd_postfix": "",
     "delete_cmd_prefix": "del ",
     "library": "var_list.py",
     "varRefreshCmd": "print(var_dic_list())"
    },
    "r": {
     "delete_cmd_postfix": ") ",
     "delete_cmd_prefix": "rm(",
     "library": "var_list.r",
     "varRefreshCmd": "cat(var_dic_list()) "
    }
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}