A whole load of binary search videos

Following yesterday's post on the linear search, I thought it would prudent to post a whole load of videos on the binary search (the linear search's big brother).

A whole load of linear search algorithm videos

The linear search: a simple algorithm for searching for something.  It is what you do when you are searching for a matching sock in your sock drawer.  Nevertheless, students find it difficult to code, so presented here is a load of videos to help.

In its simplest form, the linear search is as follows.

i = 0         // the first item in your list
found = false // you haven't found it yet
answer = null // you haven't found it
while i < numberOfItems and not(found)
    if currentItem(i) == theThingYouAreLookingFor then
        found = true  // you found it
        answer = i    // the position of the thing
    else
        i ++          // increment i
    endif
endwhile
return ( answer )

In English:

Look through all the items in your list in turn, from the start, until you find the one you are looking for.  There are two ways a linear search can end: either you find the thing (so you stop searching), or you check everything and don't find it.

#linearSearch #algorithms

dd

Linear search demo

This program demonstrates the linear search algorithm in BB4W.

The first job is to count the number of records in the input file.  Once we know this, we can set up an array of records to hold the data.  Once we have this array dimensioned we can read the data in from the file.

Once the array is populated with data, we ask the user to enter a search term.  The algorithm searches through the array linearly until the index to the required record is either found or the end of the array is reached.  We can then do useful things with this index number, for example: to display the distance from the sun.

The input file.

The output of the program.

     REM demonstrates
     REM (a) setting up a record structure
     REM (b) reading from a file
     REM (c) performing a linear search

     INSTALL @lib$+"stringlib" : REM used by FN_removeCRLF()

     file$ = @dir$+"planetsInput.txt"

     NumRecords% = FN_countRecordsInFile( file$  )


     REM now we know how many records there are
     REM we can set up a record structure
     DIM Planet{(NumRecords%-1) name$, distance }

     PROC_readDataIn( file$, Planet{()}, NumRecords% )

     REM main loop
     REPEAT
       INPUT "Enter planet name : " myplanet$
       index% = FN_search( Planet{()}, NumRecords%, myplanet$ )
       IF index%<>-999 THEN
         PRINT "Planet "Planet{(index%)}.name$
         PRINT "Distance from sun : " STR$( Planet{(index%)}.distance/1000 )" thousand km"
         PRINT "---------------------------------------------------"''
       ELSE
         PRINT "No record found"''
       ENDIF
     UNTIL FALSE


     STOP


     DEFFN_countRecordsInFile( filepath$ )
     REM opens a file for reading and counts the number of records in the file
     LOCAL file%
     LOCAL mycount%
     LOCAL dummy$
     file% = OPENIN( filepath$ )
     WHILE (NOT(EOF#file%))
       REM I know that each record has two fields
       INPUT#file%, dummy$, dummy$
       mycount% += 1 : REM count one record
     ENDWHILE
     REM REMEMBER to close the file once we are done
     CLOSE#file%
     = mycount%



     DEFPROC_readDataIn( filepath$, this{()}, n%)
     REM reads data from the file into a the data structure
     LOCAL i%
     LOCAL file%
     LOCAL name$, distance$
     file% = OPENIN( filepath$ )
     FOR i% = 0 TO n% -1
       INPUT#file%, name$, distance$
       REM remove the Carriage returns/Linefeeds
       REM and store in the structure
       this{(i%)}.name$ = FN_removeCRLF(name$)
       this{(i%)}.distance = VAL( FN_removeCRLF(distance$))
     NEXT
     REM REMEMBER to close the file once we are done
     CLOSE#file%
     ENDPROC



     DEFFN_search( this{()}, n%, key$ )
     REM performs a linear search for the key in the
     REM array of records
     LOCAL found%
     LOCAL i%
     LOCAL a%  : a% = -999 : REM assume record wont be found
     WHILE NOT(found%) AND i% < n%
       REM is the current record the one with matching key?
       IF this{(i%)}.name$ = key$ THEN
         REM yes, then found it!
         found% = TRUE
         a% = i% : REM return the index for the found record
       ELSE
         REM no
         i% += 1 : REM look for the next one
       ENDIF
     ENDWHILE
     = a%



     DEFFN_removeCRLF(t$)
     REM returns the text passed with carriage returns and line feeds removed
     LOCAL dummy%
     dummy% = FN_findreplace(t$,CHR$(13),"",0)
     dummy% = FN_findreplace(t$,CHR$(10),"",0)
     = t$



#linearSearch
#algorithms
#computing