{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Searching" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [], "source": [ "def search(x, nums):\n", " \"\"\"Finds a number in a list\n", " \n", " Paramaters:\n", " x(int): The number to search for\n", " nums (list of ints): A list of numbers\n", " \n", " Returns:\n", " The position in the list where parameter x occurs or, -1 if x is not in the list.\n", " \"\"\"\n", " try:\n", " return nums.index(x)\n", " except:\n", " return -1" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [], "source": [ "nums = [3,1,4,1,2,5]" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "-1" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "search(7, nums)" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "search(4, nums)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Sequential Searching" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "enumerate(nums)" ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[(0, 3), (1, 1), (2, 4), (3, 1), (4, 2), (5, 5)]" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "list(enumerate(nums))" ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [], "source": [ "def search(x, nums):\n", " for i,v in enumerate(nums):\n", " if v == x:\n", " return i\n", " \n", " return -1" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "search(4, nums)" ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "-1" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "search(7, nums)" ] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [], "source": [ "def sequential_search(alist, item):\n", " pos = 0\n", " found = False\n", " \n", " while pos < len(alist) and not found:\n", " if alist[pos] == item:\n", " found = True\n", " else:\n", " pos += 1\n", " \n", " return found" ] }, { "cell_type": "code", "execution_count": 24, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 24, "metadata": {}, "output_type": "execute_result" } ], "source": [ "sequential_search(nums, 4)" ] }, { "cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "False" ] }, "execution_count": 12, "metadata": {}, "output_type": "execute_result" } ], "source": [ "sequential_search(nums, 7)" ] }, { "cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [], "source": [ "def ordered_sequential_search(alist, item):\n", " pos = 0\n", " found = False\n", " stop = False\n", " \n", " while pos < len(alist) and not found and not stop:\n", " if alist[pos] == item:\n", " found = True\n", " else:\n", " if alist[pos] > item:\n", " stop = True\n", " else:\n", " pos += 1\n", " \n", " return found" ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [], "source": [ "sorted_nums = nums.copy() # shallow copy of alist" ] }, { "cell_type": "code", "execution_count": 28, "metadata": {}, "outputs": [], "source": [ "sorted_nums.sort() # If we \"forget\" to sort, what might happen?" ] }, { "cell_type": "code", "execution_count": 29, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 29, "metadata": {}, "output_type": "execute_result" } ], "source": [ "ordered_sequential_search(sorted_nums, 2)" ] }, { "cell_type": "code", "execution_count": 21, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "False" ] }, "execution_count": 21, "metadata": {}, "output_type": "execute_result" } ], "source": [ "ordered_sequential_search(sorted_nums, 7)" ] }, { "cell_type": "code", "execution_count": 18, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[3, 1, 4, 1, 2, 5]" ] }, "execution_count": 18, "metadata": {}, "output_type": "execute_result" } ], "source": [ "nums" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Binary Search" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "def binary_search(alist, item):\n", " first = 0 # blue ring\n", " last = len(alist)-1 # gold ring\n", " found = False\n", " \n", " while first <= last and not found:\n", " midpoint = (first+last)//2 # green ring, must be an int for indexing\n", " \n", " if alist[midpoint] == item:\n", " found = True\n", " elif alist[midpoint] > item: # it's in the lower half of our search space\n", " last = midpoint - 1 # move the gold ring one pos lower than mid\n", " elif alist[midpoint] < item:\n", " first = midpoint + 1 # move the blue ring on pos high than mid\n", " \n", " return found" ] }, { "cell_type": "code", "execution_count": 31, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "False" ] }, "execution_count": 31, "metadata": {}, "output_type": "execute_result" } ], "source": [ "binary_search(nums, 7)" ] }, { "cell_type": "code", "execution_count": 32, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 32, "metadata": {}, "output_type": "execute_result" } ], "source": [ "binary_search(nums, 4)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] } ], "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" } }, "nbformat": 4, "nbformat_minor": 4 }