Linear Search

Part of: Algorithms, Iteration & Simulation

Searching, finding whether and where a value lives in a list, is one of the most common tasks in computing. The simplest method is linear search : check each element in order until you find the target or run out of elements. The algorithm Linear search is just a list traversal with a goal: Key ideas: - Walk the list by index with range(len(nums)) so you can report where the match is. - Use a sentinel like -1 to mean "not found yet." - When a match is found, record the index and break out of the loop, there is no reason to keep checking. - If the loop finishes without a match, the sentinel -1 remains. Works on any list The great strength of linear search is that it makes no assumptions about the data. The list can be in any order, sorted or not, numbers or names. As long as you can compare elements for equality, linear search works. Cost and efficiency How much work is it? In the worst case : the target is last, or absent, linear search examines all n elements . We say it does work proportional to n; doubling the list roughly doubles the time. For a list of a million items, that is up to a million comparisons. On a short or unsorted list this is perfectly fine, but for large sorted

Challenge: Find the Index