{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "2271073a",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Searching and The Find Max/Min Algorithm\n",
    "#### CS 65: Introduction to Computer Science I"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1d162978",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Searching\n",
    "\n",
    "A __search__ is when you iterate through a collection, looking for values that meet a given critera.\n",
    "\n",
    "They usually involve\n",
    "* a loop that iterates through the collection\n",
    "* an if statement that checks each element for that condition\n",
    "\n",
    "We've used this pattern for solving several different kinds of problems.\n",
    "* check if a rainfall amount is in a list of rainfalls\n",
    "* checking which movie reviews contain a particular word\n",
    "* checking which zipcodes are in a given state"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "f0fda7b8",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Monday is a good day for programming\n",
      "Tuesday is a good day for programming\n",
      "Wednesday is a good day for programming\n",
      "Thursday is a good day for programming\n",
      "Friday is a good day for programming\n"
     ]
    }
   ],
   "source": [
    "days_of_the_week = [\"Sunday\",\"Monday\",\"Tuesday\",\"Wednesday\",\"Thursday\",\"Friday\",\"Saturday\"]\n",
    "\n",
    "\n",
    "for day in days_of_the_week:\n",
    "    if \"S\" not in day:\n",
    "        print(day,\"is a good day for programming\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f910c4c2",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## `min()` and `max()`\n",
    "\n",
    "The built-in `min()` and `max()` algorithms can find the largest or smallest value in a list."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "850d2e89",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "8"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "my_list = [5,1,8,7,4,2]\n",
    "max(my_list)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c1b16fc5",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "How do you think this function works?\n",
    "\n",
    "It's set up using this search pattern."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fb27ad4d",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Think about how _you'd_ remember the largest value in a list of numbers."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "e1b7ed1d",
   "metadata": {},
   "outputs": [],
   "source": [
    "student_grades = [88.3, 53.2, 76.6, 92.2, 81.9, 79.7, 62.1, 84.8, 83.3]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "e60ce6d3",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "83.3"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "student_grades[8]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e2b785b5",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "What was the biggest grade in that list?\n",
    "\n",
    "At each step, you remembered what the max-so-far was, and you compared it with the new value. At the end, whatever your max-so-far is, is the max of the whole list.\n",
    "\n",
    "Let's code this up."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1aa33778",
   "metadata": {},
   "outputs": [],
   "source": [
    "student_grades = [88.3, 53.2, 76.6, 92.2, 81.9, 79.7, 62.1, 84.8, 83.3]\n",
    "\n",
    "#in-class demo here"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "id": "2d4cda20",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The max grade is 92.2\n"
     ]
    }
   ],
   "source": [
    "#solution 1\n",
    "max_so_far = -float(\"inf\") #Python's representation of \"negative infinity\"\n",
    "\n",
    "for grade in student_grades:\n",
    "    #if I found a new max-so-far\n",
    "    if grade > max_so_far:\n",
    "        #keep track of this value as the new max-so-far\n",
    "        max_so_far = grade\n",
    "        \n",
    "print(\"The max grade is\",max_so_far)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "id": "125eeb3d",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The max grade is 92.2\n"
     ]
    }
   ],
   "source": [
    "#solution 2\n",
    "#in this version we start the max_so_far as the first item in the list\n",
    "max_so_far = student_grades[0]\n",
    "\n",
    "for grade in student_grades:\n",
    "    if grade > max_so_far:\n",
    "        max_so_far = grade\n",
    "        \n",
    "print(\"The max grade is\",max_so_far)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "88f4b5bd",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "## Group Exercise\n",
    "\n",
    "What changes do we need to make if we want to find the minimum instead of the maximum?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "cc64b5be",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "celltoolbar": "Slideshow",
  "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.8.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}