concets to pay attention to

• variable
• type
  • boolean
  • string
  • integer
  • list
• assignment
• boolean expression
• while loop
• = vs. ==
• if/else statement
• indexing
• the ++ operator
• for loop

linear search algorithm

• input: list of numbers A and a target number x

• onut: whether the list contains x . If it does, then the location at which it occurs

  

  understanding the terms

  • A: our list (2,4,0,1,9)
  • x: our target, 1
  • found: whether we've found out target (boolean)
  • i: our current position
  • n: the lenght of A, our input list, 5
  • location: the position of the element that matches the target if it exists, 4

  linear search pseudocode

  step 1: initialize our variables

  found = "no";
  i = 1;
  

  • found is a variable
  • the type of found is a boolean
  • we are assigning the value of found to be "no" to represent that our target has not been found yet
  • what should the value of found **be when we have found our target?
    • found = "yes";
  • ; denotes the end of an instruction
  • i is a variable
  • the type of i is an integer
  • we are assigning the value of i to be 1 to represent that we're starting our search from the first element of the list A
  • we will be changing the value of i. When the value of i is 2, that means we're looking at the second element of the list A

  step 2: establishing our while loop

  while (found == "no" and i <= n)
  {
  	if(A[i] == x) {
  		found = "yes"
  		location = i;
  	}
  i++;
  }
  

  • this is a while loop
    • navigates through each element in our list A
  • the while condition is a boolean expression that determins whether the loop body will execute
    • = vs ==
    • both conditions need to evaluate to true for while condition to be true
  • the loop body, or the code between the brackets, executes for each iteration of the loop
  • at the end of one iteration, the while condition is reevaluated
  • avoid infinite loops

  while (found == "no" and i <= n)
  {
  	if(A[i] == x) {
  		found = "yes"
  		location = i;
  	}
  i++;
  }
  

  

  • now we are focusing on the if statement

  • the if condition is a boolean expression that determines whether the code body will execute

  • indexing: what is A[i]?

    • the element of list A at position i

  • if the element we're looking at is equal to the target x, then we execute the body

    • set found to "yes" (we've found our target!)
    • set location to i (osition of target element)

    while (found == "no" and i <= n)
    {
    	if(A[i] == x) {
    		found = "yes"
    		location = i;
    	}
    i++;
    }
    

    • now, after executing the if statement, we do i++;
    • this means increment i by 1
    • equivalent statement: i = i+1;
    • after, we have completed the loop body
      • now we recheck the while condition to determine whether we should do the loop agin

  step 3: printing our results

  if (found == "no")
  {
  	print ("Sorry, " + x + " is not on the list");
  }
  else
  {
  	print (x + " occurs at position " + location + " on the list");
  }
  

  • if statement that executes after the while loop
  • a string is a sequence of characters expressed between double quotation marks
  • else statement is an optional addition to if statement that execuates if the if condition evaluates to false
  • if statement can exist without else, but else cannot exist without if

binary search algorithm

• always run on a sorted list of numbers

• calculates midpoint between starting and ending point
• we do the math with the indexes