Linear Search

Animation from TutorialsPoint

This algorithm is used for Strings and Lists often.

• index() and find() are linear searches

• in and not in membership for strings and lists are linear searches

Algorithm Classification

• Big-O: O(n) hence the name “Linear” Search … happens when the target is not found -or- target is the last value

• Big-Omega: O(1) very first item is the target

• Big-Theta: O(n/2) which simplifies to O(n) … target is found somewhere in the middle

Linear Search Algorithm:

Pseudocode

    # Let L be a list of items; i be the index, and N be the number of items
    # Let T be a Target
    1 Set i to 0
    2 If L at i == Target, then return i
    3 Else increase i by 1 and repeat back to Line 2
    4 If i > N, and target has not been found, then return -1

Code

Note on using a while loop

#Method 2
def linSearch(array, target):
	ctr = 0
	while ctr < len(array):
		if array[ctr] == target:
			return ctr
		ctr += 1
	else:
		return -1

Some of you may want to use a while loop with a counter rather than coding a for loop.

It is not recommended to do so because:

A while loop must check its condition on each iteration; whereas, a for loop has no looping condition to check at every iteration.