.. 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

    <center>
    <iframe type="text/javascript" src='https://cdnapisec.kaltura.com/p/2375811/embedPlaykitJs/uiconf_id/52883092?iframeembed=true&entry_id=1_s97n1vm4' style="width: 960px; height: 395px" allowfullscreen webkitallowfullscreen mozAllowFullScreen allow="autoplay *; fullscreen *; encrypted-media *" frameborder="0" title="Introduction to Searching"></iframe> 
    </center>     
     
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

   <center>
   <iframe type="text/javascript" src='https://cdnapisec.kaltura.com/p/2375811/embedPlaykitJs/uiconf_id/52883092?iframeembed=true&entry_id=1_ykrtcb3f' style="width: 960px; height: 395px" allowfullscreen webkitallowfullscreen mozAllowFullScreen allow="autoplay *; fullscreen *; encrypted-media *" frameborder="0" title="Programming Searching"></iframe> 
   </center>     
   
Programming Practice: Binary Search
-----------------------------------

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