im a beginner of coding and using python.
Im trying to code for a linear search but I don't know how to:(

## All 7 Replies

The list class 'index' method performs a linear search

``````>>> mylist = list("hello world")
>>> print(mylist)
['h', 'e', 'l', 'l', 'o', ' ', 'w', 'o', 'r', 'l', 'd']
>>> mylist.index('w')
6
>>> mylist
'w'
>>> mylist.index('z')
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
ValueError: list.index(x): x not in list``````

This also works for str objects (strings)

``````>>> mystr = "hello world"
>>> mystr.index('w')
6
>>> mystr.index('z')
Traceback (most recent call last):
File "<stdin>", line 1, in <module>

First of all, why linear search? That's like the worst algorithm to use ever.

But if you don't want to use the Python internal algorithm, a for loop can do it:

``````def findValue(v, li):
for i in len(li):
if v == len[i]:
return i
return -1``````

But that's such a bad algorithm. Internally, you have this -> `value in li` Also, you can code your own "smart" algorithm, like i did here:

``````def average(number1, number2):
return sum([number1, number2])/2

def bisectFind(li, item):
midpoint = (len(li)-1)/2
minIndex = 0
maxIndex = len(li)-1
while True:
if maxIndex - minIndex < 11:
for i in range(minIndex,maxIndex+1):
if li[i] == item:
return i
return None
if item < li[midpoint]:
maxIndex = midpoint
midpoint = average(minIndex, maxIndex)
continue
elif item > li[midpoint]:
minIndex = midpoint
midpoint = average(minIndex, maxIndex)
continue
elif item == li[midpoint]:
return midpoint``````

First of all, why linear search? That's like the worst algorithm to use ever.

But if you don't want to use the Python internal algorithm, a for loop can do it:

``````def findValue(v, li):
for i in len(li):
if v == len[i]:
return i
return -1``````

But that's such a bad algorithm. Internally, you have this -> `value in li` Also, you can code your own "smart" algorithm, like i did here:

``````def average(number1, number2):
return sum([number1, number2])/2

def bisectFind(li, item):
midpoint = (len(li)-1)/2
minIndex = 0
maxIndex = len(li)-1
while True:
if maxIndex - minIndex < 11:
for i in range(minIndex,maxIndex+1):
if li[i] == item:
return i
return None
if item < li[midpoint]:
maxIndex = midpoint
midpoint = average(minIndex, maxIndex)
continue
elif item > li[midpoint]:
minIndex = midpoint
midpoint = average(minIndex, maxIndex)
continue
elif item == li[midpoint]:
return midpoint``````

Binary search works only if the list is initially sorted.

commented: good catch +10

yeah that's true too. I actually didn't figure out how it works until a couple minutes ago. Wrote this a long time ago and didn't put a comment.

A linear search goes through a sequence of items one item at a time from the start of the sequence until the item is found ...

``````sequence = 'abcdefghijklmnopqrstuvwxyz'
search = 'z'
for c in sequence:
if c == search:
print("found search item")
break``````

As you can see, if you were looking for 'a' it would be very efficient, but if you were looking for 'z' it would be the least efficient. If the size of your sequence is relatively small, a linear search is okay. However, imagine a sequence of a million or more items and your search item is near the end.

``````def binary_search(a, n, required):
start = 0
end = n - 1
while start <= end:
middle = (end + start) / 2
if a[middle] == required:
break
else:
if required < a[middle]:
end = middle - 1
else:
start = middle + 1

array = (1, 2, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14)
print binary_search(array, len(array), 4)``````

slightly faster,
Requires array sorting!

I would little clean up -ordi- code:

``````def binary_search(a, required):
start = 0
end = len(a) - 1
while start <= end:
middle = (end + start) / 2
if a[middle] == required:
break
elif required < a[middle]:
end = middle - 1
else:
start = middle + 1