Skip to content

Instantly share code, notes, and snippets.

@Shurlow

Shurlow/searching.md

Last active September 22, 2022 11:52
Show Gist options
  • Save Shurlow/e29019806741a0ac5c257b03b89d2f60 to your computer and use it in GitHub Desktop.
Save Shurlow/e29019806741a0ac5c257b03b89d2f60 to your computer and use it in GitHub Desktop.
Download ZIP
Searching & Sorting Lesson Notes
Raw
searching.md

Searching

Objectives

  • Write pseudocode for linear search
  • Write pseudocode for binary search
  • Translate algorithm pseudocode to working code
  • Describe the Big O complexity of linear and binary search

Guiding Questions

  • Take a minute to look over these examples of pseudocode for a selectEvenNumbers function. Which one do you prefer? Why?

    Style 1:
    function selectEvenNumbers takes 1 parameter, numbers (array of integers)

create evenNumbers variable and set to an empty array

for each num in numbers array
  check if num is even
    add num to evenNumers array

return evenNumbers
    Style 2:
    Function selectEvenNumbers
  Input: numbers -> array integers
  Output: array of integers

set evenNumbers -> []

for i = 0 to i = numbers.length
  if (numbers[i] % 2 === 0)
    push numbers[i] onto evenNumbers

return evenNumbers
    Linear Search

    Given an array of integers, numbers, and a value val, a linearSearch() function should return the index of val in numbers. If val does not exist in numbers, return -1.

    Your answer...

  • What is the Big O complexity of Linear Search?

    Your answer...

  • How does binary search work in your own words. What condition needs to be met to use binary search on an array?

    Your answer...

  • Write pseudocode for Binary Search. Start by forking this: https://repl.it/@galvanize/BinarySearch

    Your answer...

  • Translate your pseudocode from above to working code.

    Your answer...

  • What is the Big O complexity of Binary Search?

    Your answer...

Resources

Raw
sorting.md

Sorting

Objectives

  • Write pseudocode for Selection Sort
  • Write working code for Selection Sort
  • Describe the Big O complexity of Selection Sort
  • Write pseudocode for Merge Sort
  • Write working code for Merge Sort
  • Describe the Big O complexity of Merge Sort

Guiding Questions

  • Write pseudocode for Selection Sort.

    Your answer...

  • Translate pseudocode into working code for Selection Sort.

    Your answer...

  • What is the Big O complexity of Selection Sort.

    Your answer...

  • Write pseudocode for Merge Sort. Start from this example: https://repl.it/@galvanize/MergeSort

    Your answer...

  • Translate pseudocode into working code for Merge Sort.

    Your answer...

  • What is the Big O complexity of Merge Sort.

    Your answer...

Resources

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment