.. 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 [10:14]
---------------------------------

.. 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/meng-bridge/course-notes/12.2.2.1-IntroToSearching.pdf" target="_blank">
         <img src="https://courses.cs.vt.edu/~cs2114/meng-bridge/images/projector-screen.png" alt="" width="32" height="32">
         Video Slides 12.2.2.1-IntroToSearching.pdf</img>
         </a>

.. raw:: html

   <div style="position: relative; width: 100%; height: 0; padding-bottom: 35%">
     <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/MengBridgeCourse/BinarySearchCheckpoint1Summ.html ka
   :long_name: Checkpoint 1

Programming Searching [20:22]
-----------------------------
   
.. 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/meng-bridge/course-notes/12.2.4.1-ProgrammingSearching.pdf" target="_blank">
        <img src="https://courses.cs.vt.edu/~cs2114/meng-bridge/images/projector-screen.png" alt="" width="32" height="32">
        Video Slides 12.2.4.1-ProgrammingSearching.pdf</img>
        </a>
        
.. raw:: html

  <div style="position: relative; width: 100%; height: 0; padding-bottom: 35%">
       <iframe src="https://virginiatech.hosted.panopto.com/Panopto/Pages/Embed.aspx?id=83c9cfd3-5f23-4d63-8ee7-b40400ec81c9&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