im a beginner of coding and using python.
Im trying to code for a linear search but I don't know how to:(
- 6 Contributors
- forum7 Replies
- 11 Views
- 8 Years Discussion Span
- comment Latest Post by pyTony
Gribouillis 1,391
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[6]
'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>
ValueError: substring not found
Edited
by Gribouillis: n/a
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
Gribouillis 1,391
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.
vegaseat
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.
vegaseat 1,720
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.
Edited
by vegaseat: least
-ordi- 6
def binary_search(a, n, required):
start = 0
end = n - 1
answer = 0
while start <= end:
middle = (end + start) / 2
if a[middle] == required:
answer = middle
break
else:
if required < a[middle]:
end = middle - 1
else:
start = middle + 1
return answer
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!
Edited
by -ordi-: n/a
pyTony 888
I would little clean up -ordi- code:
def binary_search(a, required):
start = 0
end = len(a) - 1
answer = None
while start <= end:
middle = (end + start) / 2
if a[middle] == required:
answer = middle
break
elif required < a[middle]:
end = middle - 1
else:
start = middle + 1
return answer
array = (1, 2, 4, 5, 6, 7, 8, 10, 11, 12, 13, 14)
print binary_search(array, 9) ## not there
print binary_search(array, 4) ## index 2