1) 이진 탐색(Binary Search).ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 탐색 알고리즘 - 이진 탐색 (Binary Search)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1. 이진 탐색 (Binary Search) 이란?\n",
    "* 탐색할 자료를 둘로 나누어 해당 데이터가 있을만한 곳을 탐색하는 방법"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "solution2": "shown",
    "solution2_first": true
   },
   "source": [
    "### 다음 문제를 먼저 생각해보자\n",
    "<img src=\"https://www.fun-coding.org/00_Images/binarysearch.png\" width=\"700\" />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "solution2": "shown"
   },
   "source": [
    "### 이진 탐색의 이해 (순차 탐색과 비교하며 이해하기)\n",
    "\n",
    "<img src=\"https://www.mathwarehouse.com/programming/images/binary-vs-linear-search/binary-and-linear-search-animations.gif\">\n",
    "\n",
    "* [저작자] by penjee.com [이미지 출처](https://blog.penjee.com/binary-vs-linear-search-animated-gifs)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2. 분할 정복 알고리즘과 이진 탐색\n",
    "- 분할 정복 알고리즘 (Divide and Conquer)\n",
    "  - Divide: 문제를 하나 또는 둘 이상으로 나눈다.\n",
    "  - Conquer: 나눠진 문제가 충분히 작고, 해결이 가능하다면 해결하고, 그렇지 않다면 다시 나눈다.\n",
    "- 이진 탐색\n",
    "  - Divide: 리스트를 두 개의 서브 리스트로 나눈다.\n",
    "  - Conquer\n",
    "    - 검색할 숫자 (search) > 중간값 이면, 뒷 부분의 서브 리스트에서 검색할 숫자를 찾는다.\n",
    "    - 검색할 숫자 (search) < 중간값 이면, 앞 부분의 서브 리스트에서 검색할 숫자를 찾는다.  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### 3. 어떻게 코드로 만들까?\n",
    "* 이진 탐색은 데이터가 정렬되있는 상태에서 진행\n",
    "* 데이터가 [2, 3, 8, 12, 20] 일 때,\n",
    "  - binary_search(data_list, find_data) 함수를 만들고\n",
    "    - find_data는 찾는 숫자\n",
    "    - data_list는 데이터 리스트\n",
    "    - data_list의 중간값을 find_data와 비교해서\n",
    "      - find_data < data_list의 중간값 이라면\n",
    "        - 맨 앞부터 data_list의 중간까지 에서 다시 find_data 찾기\n",
    "      - data_list의 중간값 < find_data 이라면\n",
    "        - data_list의 중간부터 맨 끝까지에서 다시 find_data 찾기\n",
    "      - 그렇지 않다면, data_list의 중간값은 find_data 인 경우로, return data_list 중간위치"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4. 알고리즘 구현"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [],
   "source": [
    "def binary_search(data, search):\n",
    "    print (data)\n",
    "    if len(data) == 1 and search == data[0]:\n",
    "        return True\n",
    "    if len(data) == 1 and search != data[0]:\n",
    "        return False\n",
    "    if len(data) == 0:\n",
    "        return False\n",
    "    \n",
    "    medium = len(data) // 2\n",
    "    if search == data[medium]:\n",
    "        return True\n",
    "    else:\n",
    "        if search > data[medium]:\n",
    "            return binary_search(data[medium+1:], search)\n",
    "        else:\n",
    "            return binary_search(data[:medium], search)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[69, 65, 18, 71, 11, 10, 42, 68, 36, 89]"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import random\n",
    "data_list = random.sample(range(100), 10)\n",
    "data_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [],
   "source": [
    "data_list.sort()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[10, 11, 18, 36, 42, 65, 68, 69, 71, 89]"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "data_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[10, 11, 18, 36, 42, 65, 68, 69, 71, 89]\n",
      "[68, 69, 71, 89]\n",
      "[68, 69]\n",
      "[68]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "binary_search(data_list, 66)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5. 알고리즘 분석\n",
    "* n개의 리스트를 매번 2로 나누어 1이 될 때까지 비교연산을 k회 진행\n",
    "  - <font size=4em>n X $\\frac { 1 }{ 2 }$ X $\\frac { 1 }{ 2 }$ X $\\frac { 1 }{ 2 }$ ... = 1</font>\n",
    "  - <font size=4em>n X $\\frac { 1 }{ 2 }^k$ = 1</font>\n",
    "  - <font size=4em>n = $2^k$ = $log_2 n$ = $log_2 2^k$</font>\n",
    "  - <font size=4em>$log_2 n$ = k</font>\n",
    "  - 빅 오 표기법으로는 k + 1 이 결국 최종 시간 복잡도임 (1이 되었을 때도, 비교연산을 한번 수행)\n",
    "    - 결국 O($log_2 n$ + 1) 이고, 2와 1, 상수는 삭제 되므로, O($log n$)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class=\"alert alert-block alert-warning\">\n",
    "<strong><font color=\"blue\" size=\"4em\">프로그래밍 연습</font></strong><br>\n",
    "다음 10000개의 데이터를 삽입 정렬, 퀵 정렬로 정렬하는 함수를 각각 만들어보고, 각각의 정렬 시간을 출력하기<br>\n",
    "</div>\n",
    "\n",
    "```python\n",
    "# 데이터 셋\n",
    "import random \n",
    "data_list = random.sample(range(100000), 10000)\n",
    "\n",
    "# 현재 시간 구하기\n",
    "import datetime\n",
    "print (datetime.datetime.now())\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def insertion_sort(data):\n",
    "    for i in range(len(data)):\n",
    "        key = data[i]\n",
    "        for k in range(i, 0, -1):\n",
    "            if key < data[k - 1]:\n",
    "                data[k], data[k - 1] = data[k - 1], data[k]\n",
    "            else:\n",
    "                break"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "def quick_sort(data):\n",
    "    if len(data) <= 1:\n",
    "        return data\n",
    "    pivot = data[0]\n",
    "    left = [item for item in data[1:] if item < pivot]\n",
    "    right = [item for item in data[1:] if item >= pivot]\n",
    "    return quick_sort(left) + [pivot] + quick_sort(right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "import datetime"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2020-05-23 23:05:42.317515\n",
      "2020-05-23 23:05:49.489651\n"
     ]
    }
   ],
   "source": [
    "data = random.sample(range(100000), 10000)\n",
    "print(datetime.datetime.now())\n",
    "insertion_sort(data)\n",
    "print(datetime.datetime.now())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2020-05-23 23:05:58.008233\n",
      "2020-05-23 23:05:58.049154\n"
     ]
    }
   ],
   "source": [
    "data = random.sample(range(100000), 10000)\n",
    "print(datetime.datetime.now())\n",
    "quick_sort(data)\n",
    "print(datetime.datetime.now())"
   ]
  }
 ],
 "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.6.9"
  },
  "nbTranslate": {
   "displayLangs": [
    "*"
   ],
   "hotkey": "alt-t",
   "langInMainMenu": true,
   "sourceLang": "en",
   "targetLang": "fr",
   "useGoogleTranslate": true
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}