YouTube

Got a YouTube account?

New: enable viewer-created translations and captions on your YouTube channel!

English subtitles

← Find Element Solution - Intro to Computer Science

Get Embed Code
5 Languages

Showing Revision 6 created 05/24/2016 by Udacity Robot.

  1. [Evans] There are many different ways we could solve this problem.
  2. First we'll look at a way of solving it using a while loop.
  3. We'll define our find_element procedure.
  4. We'll use p as the name of the list and t as the name of the target,
  5. the element that we want to match.
  6. We'll define the loop to go through the elements of p,
  7. similarly to the previous while loops we've seen that go through lists.
  8. We have our while loop. We've introduced the variable i.
  9. We'll use that as the index to go through the loop.
  10. The stopping condition for the while loop is when i reaches the len(p),
  11. so we want our test for the while loop to be i < len(p).
  12. In the block of the while loop we want to check if the current element matches t,
  13. so we get the current element using p[i] and then we use == to test if it's equal to t.
  14. If we find a match, meaning the 2 values are equal,
  15. then we want to return the index that we found.
  16. So the result should be the value of i,
  17. which is the index where we found the matching element.
  18. The risky thing about using while loops instead of for-loops
  19. is it's really easy to forget that you need to increase the index variable.
  20. If we just left the loop like this, it would run forever
  21. because the value of i would never change unless the first element matched,
  22. in which case we would return 0.
  23. The loop would just keep going on forever, again checking the first element.
  24. So we need to increase the value of i,
  25. and that's the end of the while block.
  26. The way we described what the find_element procedure should do,
  27. if the element was not found, it should return -1.
  28. If we get to the end of the while loop without returning,
  29. that means we've gone through the while loop for all values of i up to len(p) - 1.
  30. We didn't find any element that matches, so we should return -1.
  31. So that's one way to define find_element.
  32. I'll also show you a way to define it using a for-loop.
  33. The reason it's more natural to start thinking of defining find_element with a while loop
  34. than a for-loop is because the value that we want to return from find_element
  35. is the index itself.
  36. When we use a for-loop with the standard syntax of going through the elements
  37. of the loop, we don't keep track of the index.
  38. We just see each element in order.
  39. So we need to add something else to keep track of the index
  40. because that's the value we want to return.
  41. So we still need to use a variable to keep track of the index.
  42. We'll use i as that variable just like we did in the while loop version.
  43. Now instead of a while loop we'll have a for-loop.
  44. We don't need to think of the stopping condition here
  45. because it will just go through all the elements.
  46. Similarly to the body of the while loop, we check if the current element is equal to t.
  47. In the for-loop we can get the current element using the variable e.
  48. That's what gets assigned each time we go through the loop body
  49. to the value of the current element.
  50. So our test is using == to compare e and t.
  51. If they match, just like we did in the while version, we should return the result.
  52. The result we want to return is the index where we found the match.
  53. In the while version that was clear.
  54. It made sense because we were looking at element p, index i.
  55. In the version with the for-loop we have to be more careful to know where that index is.
  56. We're using the variable i to keep track of that index, so we'll return i.
  57. i starts at 0.
  58. Each time through the loop we need to increase i
  59. so we keep track of the current index as we go through the elements.
  60. As with the previous definition, when we had the while loop,
  61. if we got to the end without finding it, that meant that the element did not exist in p
  62. and we should return -1.
  63. We'll do the same thing here.