.. This file is part of the OpenDSA eTextbook project. See
.. http://opendsa.org for more details.
.. Copyright (c) 2012-2020 by the OpenDSA Project Contributors, and
.. distributed under an MIT open source license.

.. avmetadata::
   :author: Molly Domino

Binary Search
=============

Objectives
----------

Upon completion of this module, students will be able to:

* Trace linear and binary searches
* Evaluate efficiency of linear and binary searches
* Implement linear and binary searches

Introduction to Searching 
---------------------------------

.. admonition:: Follow Along and Engage

    Download the slides corresponding to the video. Take notes on them as you watch the video, practice drawing diagrams yourself!

   .. raw:: html

      <a href="https://courses.cs.vt.edu/cs2114/SWDesignAndDataStructs/course-notes/IntroToSearching.pdf"  target="_blank">
      <img src="https://courses.cs.vt.edu/cs2114/opendsa/icons/projector-screen.png" alt="" width="32" height="32">
      IntroToSearching.pdf</a>

.. raw:: html
     
   <div style="position: relative; width: 100%; height: 0; padding-bottom: 38%">
         <iframe src="https://virginiatech.hosted.panopto.com/Panopto/Pages/Embed.aspx?id=28d44ac5-eb58-4f52-9926-b4150129c2e2&autoplay=false&offerviewer=true&showtitle=true&showbrand=true&captions=false&interactivity=all" style="border: 1px solid #464646; position: absolute; top: 0; left: 0; width: 960px; height: 395px; box-sizing: border-box;" allowfullscreen allow="autoplay" aria-label="Introduction to Searching " aria-description="Introduction to Searching "></iframe>
      </div>

Checkpoint 1
------------

.. avembed:: Exercises/SWDesignAndDataStructs/BinarySearchCheckpoint1Summ.html ka
   :long_name: Checkpoint 1


Programming Searching
-----------------------------

.. admonition:: Follow Along and Engage

    Download the slides corresponding to the video. Take notes on them as you watch the video, practice drawing diagrams yourself!

   .. raw:: html

      <a href="https://courses.cs.vt.edu/cs2114/SWDesignAndDataStructs/course-notes/ProgrammingSearching.pdf"  target="_blank">
      <img src="https://courses.cs.vt.edu/cs2114/opendsa/icons/projector-screen.png" alt="" width="32" height="32">
      ProgrammingSearching.pdf</a>

.. raw:: html

   <div style="position: relative; width: 100%; height: 0; padding-bottom: 38%">
         <iframe src="https://virginiatech.hosted.panopto.com/Panopto/Pages/Embed.aspx?id=be87ac31-7598-4e98-be37-b42400f03637&autoplay=false&offerviewer=true&showtitle=true&showbrand=true&captions=false&interactivity=all" style="border: 1px solid #464646; position: absolute; top: 0; left: 0; width: 960px; height: 395px; box-sizing: border-box;" allowfullscreen allow="autoplay" aria-label="Programming Searching" aria-description="Programming Searching"></iframe>
      </div>   
   
Programming Practice: Binary Search
-----------------------------------

.. extrtoolembed:: 'Programming Practice: Binary Search'
   :workout_id: 1927