Из курса «Searching and sorting algorithms (CS50 Shorts)»
0 просмотров · 6 ноября 2026
How to find a value in a list by checking each item in turn, and why that is the only option when the list is not in order. Source: CS50 Shorts, "Linear Search" by CS50, Harvard University Original: https://cs50.harvard.edu/x/2024/shorts/linear_search/ Licence: CC BY-NC-SA 4.0 (https://creativecommons.org/licenses/by-nc-sa/4.0/) Changes: Re-encoded; captions, summary and thumbnail generated by Upgram. Not endorsed by CS50 or Harvard University. Shared under the same licence.
Learn how linear search checks an array from left to right until it finds a target or reaches the end, and how its best- and worst-case running times are described. This is useful for understanding a simple search method and how algorithm efficiency depends on where the target appears. In the worst case, every element must be checked, so the runtime is O(n); the best case takes one check, or Ω(1).
. Linear search is an algorithm we can use to find an element in an array. An algorithm, recall, is a step-by-step set of instructions for completing a task. The linear search algorithm works as follows. Iterate across the array from left to right, looking for a specified element. In pseudocode, it's just a more distilled version of this sentence, if the first element is what you're looking for, you can stop. Otherwise, move to the next element. And keep going over and over until you find the element or you don't. So we can use the linear search algorithm, for example, to find the target value 9 in this array. Well, we start at the beginning. If it's what we're looking for, we can stop. It's not. We're not looking for 11. So otherwise, move to the next element. So we look at 23. Is 23 what we're looking for? Well, no. So we move on to the next element and the next element. And we keep going through this process over and over and over until we land on a situation like this. 9 is what we're looking for. And this element of the array is value is 9. And so we found what we're looking for. And we can stop. The linear search has completed successfully. But what about if we're looking for an element that's not in our array? Does linear search still work? Well, sure. So we repeat this process starting at the first element. If it's what we're looking for, we can stop. It's not. Otherwise, we move to the next element. And we can keep repeating this process, examining each element in turn, hoping that we find the number 50. But we won't know if we found the number 50 or if we didn't until we've stepped over every single element of the array. Only once we've done that and come up short can we conclude that 50 is not in the array. And so the linear search algorithm, well, it failed per se, but not in the sense that it was unsuccessful in doing what we asked it to do. It was unsuccessful in as much as it didn't find 50, but 50 wasn't in the array. But we have exhaustively searched through every single element. And so while we didn't find anything, linear search still succeeds, even if the element is not in the array. So what's the worst case scenario with linear search? Well, we have to look through every single element, either because the target element is the last element of the array, or the element we're looking for or doesn't actually exist in the array at all. What's the best case scenario? Well, we might find the element immediately. And how many elements do we then have to look at in the best case, if we're looking for it and we find it at the very beginning? We can stop immediately. What does this say about the complexity of linear search? Well, in the worst case, we have to look at every single element. And so it runs in O of n in the worst case. In the best case, we're going to find the element immediately. And so it runs in omega of 1. I'm Doug Lloyd. This is CS50.
Чтобы продолжить, установите приложение
Ставьте «Нравится», комментируйте, подписывайтесь на авторов и следите за прогрессом в приложении Upgram.
Скачать Upgram
Комментарии