01数据结构与算法.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": [],
      "authorship_tag": "ABX9TyPD6+4Q7GKx7fCb2rOfvLy9",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/zzqnot996/coding/blob/main/pythonn%E5%86%85%E7%BD%AE%E7%9A%84%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 12,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "wabKMGFMkjDo",
        "outputId": "0772bddb-c3b8-4b3c-c254-ddeb7306c9de"
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "target:\t 675653\n"
          ]
        }
      ],
      "source": [
        "import timeit\n",
        "import random\n",
        "arr = [i for i in range(1000000)]\n",
        "target = random.choice(arr)\n",
        "print('target:\\t',target)\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 16,
      "metadata": {
        "id": "I2jHpKjmr6Y5"
      },
      "outputs": [],
      "source": [
        "\n",
        "\n",
        "def traverse(array,target):\n",
        "  \"\"\"随机查找\"\"\"\n",
        "  for number in array:\n",
        "    if target == number:\n",
        "      return number\n",
        "  return False\n",
        "\n",
        "\n",
        "def binary_search_normal(array,data) :\n",
        "  \"\"\"二分查找法 - 非递归实现\"\"\"\n",
        "  start,end = 0,len(array) - 1\n",
        "  while start <= end:\n",
        "    mid_index = (start + end) // 2\n",
        "    if array[mid_index] == data:\n",
        "      # 如果查询到就返回\n",
        "      return array.index(data)\n",
        "    if data > array[mid_index]:\n",
        "      start = mid_index + 1\n",
        "    else:\n",
        "      end = mid_index - 1\n",
        "  return False\n",
        "\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 17,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "eab84684-b204-43ec-ac35-296632c8fb1c",
        "id": "3zREY_N1rx8J"
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "traverse: 0.986643\n",
            "binary: 0.433293\n"
          ]
        }
      ],
      "source": [
        "\n",
        "setup1 = \"\"\"\n",
        "from __main__ import traverse;\n",
        "import random;\n",
        "array = [i for i in range(1000000)];\n",
        "target = random.choice(array)\n",
        "\"\"\"\n",
        "setup2=\"\"\"\n",
        "from __main__ import binary_search_normal;\n",
        "import random;\n",
        "array = [i for i in range(1000000)];\n",
        "target = random.choice(array)\n",
        "\"\"\"\n",
        "timer1 = timeit.Timer(stmt=\"traverse(array,target)\",setup=setup1)\n",
        "timer2 = timeit.Timer(stmt=\"binary_search_normal(array,target)\",setup=setup2)\n",
        "\n",
        "print(\"traverse: %f\" % timer1.timeit(number=100))\n",
        "print(\"binary: %f\"% timer2.timeit(number=100))"
      ]
    }
  ]
}