{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "4729fb96",
   "metadata": {},
   "source": [
    "# Algorithmes de recherche dans les tableaux\n",
    "\n",
    "Le module `utils`, founi avec les notebooks, définit le type `IntArray` et des fonctions de création de tablaux."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "85e0de92",
   "metadata": {},
   "outputs": [],
   "source": [
    "from utils import *\n",
    "import timeit\n",
    "import random\n",
    "import matplotlib.pyplot as plt\n",
    "import numpy as np"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "50aa13a1",
   "metadata": {},
   "source": [
    "## Recherche linéaire\n",
    "\n",
    "Recherche la première occurrence de `x` dans le tableau d'entiers `t`\n",
    "\n",
    "- **PRECOND:** `t` est un tableau d'entiers, et `x` est un entier\n",
    "- **POSTCOND:** si `x` appartient à `t`, alors `findFirst` retourne le plus petit entier `i` entre `0` et `t.size-1` tel que `t[i] = x`, sinon `findFirst` retourne `None`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6e4524bc",
   "metadata": {},
   "outputs": [],
   "source": [
    "def findFirst(t: IntArray, x: int) -> int | None:\n",
    "    for i in range(t.size):\n",
    "        if x == t[i]:\n",
    "            return i\n",
    "    return None"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "49a190d7",
   "metadata": {},
   "source": [
    "## Recherche linéaire dans un tableau trié\n",
    "\n",
    "Recherche la première occurrence de `x` dans un tableau d'entiers `t` **trié**\n",
    "\n",
    "- **PRECOND:** `t` est un tableau d'entiers **trié**, et `x` est un entier\n",
    "- **POSTCOND:** si `x` appartient à `t`, alors `findFirstSorted` retourne le plus petit entier `i` entre `0` et `t.size-1` tel que `t[i] = `, sinon `findFirstSorted` retourne `None`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c94427f7",
   "metadata": {},
   "outputs": [],
   "source": [
    "def findFirstSorted(t: IntArray, x: int) -> int | None:\n",
    "    for i in range(t.size):\n",
    "        if x == t[i]:\n",
    "            return i\n",
    "        elif x < t[i]:\n",
    "            return None\n",
    "    return None"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8ce4c0bb",
   "metadata": {},
   "source": [
    "## Recherche dichotomique dans un tableau trié\n",
    "\n",
    "Recherche de `x` dans le tableau d'entiers `t` **trié**\n",
    "\n",
    "- **PRECOND:** `t` est un tableau d'entiers **trié**, et `x` est un entier\n",
    "- **POSTCOND:** si `x` appartient à `t`, alors `findBin` retourne un entier `i` entre `0` et `t.size-1` tel que `t[i] = x`, sinon `findBin` retourne `None`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b5a5374f",
   "metadata": {},
   "outputs": [],
   "source": [
    "def findBin(t: IntArray, x: int) -> int | None:\n",
    "    l: int = 0; r: int = t.size - 1;\n",
    "    while l <= r:\n",
    "        p:int = (l + r) // 2\n",
    "        if t[p] == x:\n",
    "            return p\n",
    "        elif t[p] < x:\n",
    "            l = p + 1\n",
    "        else:\n",
    "            r = p - 1\n",
    "    return None"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dbb91324",
   "metadata": {},
   "source": [
    "## Comparaison expérimentale des algorithmes de recherche"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "05f10e47",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Mesure des temps de calcul\n",
    "\n",
    "# Taille max du tableau et valeur max de x\n",
    "MAX_SIZE = 100000\n",
    "\n",
    "# Nombre d'expériences\n",
    "SAMPLE_SIZE = 1000\n",
    "\n",
    "sizes = np.empty(SAMPLE_SIZE)\n",
    "times_lin = np.empty(SAMPLE_SIZE)\n",
    "times_lin_sorted = np.empty(SAMPLE_SIZE)\n",
    "times_bin = np.empty(SAMPLE_SIZE)\n",
    "\n",
    "for i in range(SAMPLE_SIZE):\n",
    "    size = random.randint(1, MAX_SIZE + 1)\n",
    "    t = newSortedRandomIntArray(size, 0, size)\n",
    "    x = random.randint(-size // 10, size)\n",
    "    sizes[i] = size\n",
    "    times_lin[i] = timeit.timeit(lambda: findFirst(t, x), number=5)\n",
    "    times_lin_sorted[i] = timeit.timeit(lambda: findFirstSorted(t, x), number=5)\n",
    "    times_bin[i] = timeit.timeit(lambda: findBin(t, x), number=5)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2800fcf0",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Graphe des temps d'exécution\n",
    "\n",
    "fig, axs = plt.subplots(1, 3, figsize=(12, 8))\n",
    "\n",
    "# Recherche linéaire\n",
    "axs[0].set_title(\"Recherche linéaire\")\n",
    "axs[0].scatter(sizes, times_lin, alpha=0.2)\n",
    "axs[0].set_xlabel(\"taille n\")\n",
    "axs[0].set_ylabel(\"temps (s)\")\n",
    "\n",
    "# Recherche linéaire dans un tableau trié\n",
    "axs[1].set_title(\"Recherche linéaire (tableau trié)\")\n",
    "axs[1].scatter(sizes, times_lin_sorted, alpha=0.2)\n",
    "axs[1].set_xlabel(\"taille n\")\n",
    "axs[1].set_ylabel(\"temps (s)\")\n",
    "\n",
    "# Recherche dichotomique\n",
    "axs[2].set_title(\"Recherche dichotomique\")\n",
    "axs[2].scatter(sizes, times_bin, alpha=0.2)\n",
    "axs[2].set_xlabel(\"taille n\")\n",
    "axs[2].set_ylabel(\"temps (s)\")\n",
    "\n",
    "# Les trois ensemble\n",
    "fig2, axs2 = plt.subplots(figsize=(12, 10))\n",
    "axs2.scatter(sizes, times_lin, label='linéaire', alpha=0.2)\n",
    "axs2.scatter(sizes, times_lin_sorted, label='linéaire (trié)', alpha=0.2)\n",
    "axs2.scatter(sizes, times_bin, label='dichotomique', alpha=0.2)\n",
    "axs2.legend()\n",
    "axs2.set_xlabel(\"taille n\")\n",
    "axs2.set_ylabel(\"temps (s)\")\n",
    "\n",
    "plt.show()\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "defaultInterpreterPath: 3.14.7.final.0",
   "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.14.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}