{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "33648af8-a3ca-4444-b7cf-e495eb43ba7d",
   "metadata": {},
   "source": [
    "### <center>San Jose State University<br>Department of Applied Data Science<br><br>**DATA 200<br>Computational Programming for Data Analytics**<br><br>Spring 2024<br>Instructor: Ron Mak</center>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d7c61a83-5a32-49e2-9461-c06f87b035c7",
   "metadata": {},
   "source": [
    "# Recursive Binary Search\n",
    "#### The binary search algorithm implemented recursively."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "4f777390-3c1a-4f24-8435-910b8a6b772d",
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import random\n",
    "import time\n",
    "import matplotlib.pyplot as plt\n",
    "import seaborn as sns\n",
    "\n",
    "%matplotlib inline"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "91b6d06b-ca24-4c77-ba1b-c1253e988f8d",
   "metadata": {},
   "outputs": [],
   "source": [
    "def sorted_values(size):\n",
    "    return list(range(0, 2*size, 2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "6d57e6cd-f998-4a02-94ee-7f93ceeeff78",
   "metadata": {},
   "outputs": [],
   "source": [
    "SEARCH_COUNT = 100_000\n",
    "SIZES = list(range(0, 1_000_001, 100_000))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "63dd4d85-4aa2-4367-b109-533419109085",
   "metadata": {},
   "source": [
    "## Recursive binary search function"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "9863eb2b-7b7b-46ec-9064-0b9bf4cdff5d",
   "metadata": {},
   "outputs": [],
   "source": [
    "def recursive_binary_search(target, values, low, high):\n",
    "    \"\"\"\n",
    "    Perform a recursive binary search of a sorted list\n",
    "    for a target value.\n",
    "    @param target the value to search for.\n",
    "    @param values the sorted list.\n",
    "    @return 1 if found else 0.\n",
    "    \"\"\"\n",
    "    if low <= high:\n",
    "        mid = (low + high)//2\n",
    "\n",
    "        # Found!\n",
    "        if target == values[mid]:\n",
    "            return 1\n",
    "\n",
    "        # Next search lower half.\n",
    "        elif target < values[mid]:\n",
    "            return recursive_binary_search(target, values, low, mid - 1)\n",
    "\n",
    "        # Next search upper half.\n",
    "        else:\n",
    "            return recursive_binary_search(target, values, mid + 1, high)\n",
    "\n",
    "    # Not found.\n",
    "    else:\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "e96dee82-a4a6-42cb-8309-ea42fefae239",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "size =         0 count =      0\n",
      "size =   100,000 count = 49,986\n",
      "size =   200,000 count = 50,138\n",
      "size =   300,000 count = 49,944\n",
      "size =   400,000 count = 50,059\n",
      "size =   500,000 count = 50,010\n",
      "size =   600,000 count = 50,043\n",
      "size =   700,000 count = 49,447\n",
      "size =   800,000 count = 50,276\n",
      "size =   900,000 count = 49,999\n",
      "size = 1,000,000 count = 49,972\n"
     ]
    }
   ],
   "source": [
    "times = []\n",
    "\n",
    "for size in SIZES:\n",
    "    values = sorted_values(size)\n",
    "    count = 0\n",
    "\n",
    "    for _ in range(SEARCH_COUNT):\n",
    "        target_value = random.randint(0, size)\n",
    "        count += recursive_binary_search(target_value, values, 0, len(values) - 1)\n",
    "\n",
    "    print(f'{size = :9,d} {count = :6,d}')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "90ea5102-7637-4445-9cc4-77814f948555",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.11.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}