onlyforbopi
12/22/2016 - 2:50 PM

## Python.Data.Searching

Python.Data.Searching #python #Python #binarysearch #sequentialsearch #binary #sequential #indexsearch #searching #dictsearch

PYTHON SEARCHING

``````def binarySearch(alist, item):
'''
Function: binarySearch
Description: Binary search on list
Input: List
Output: Tuple of boolean, index
Usage: binarySearch(list, item)
Notes: Does not edit list in place, recursive
'''
if len(alist) == 0:
return False
else:
midpoint = len(alist)//2
if alist[midpoint]==item:
return (True, midpoint)
else:
if item<alist[midpoint]:
return binarySearch(alist[:midpoint],item)
else:
return binarySearch(alist[midpoint+1:],item)

testlist = [0, 1, 2, 8, 13, 17, 19, 32, 42,]
print(binarySearch(testlist, 3))
print(binarySearch(testlist, 13))

def binarySearch(alist, item):
'''
Function: binarySearch
Description: Binary search on list
Input: List
Output: Tuple of boolean, index
Usage: binarySearch(list, item)
Notes: Does not edit list in place, recursive
'''
first = 0
last = len(alist)-1
found = False

midpoint = (first + last)//2
if alist[midpoint] == item:
found = True
else:
if item < alist[midpoint]:
last = midpoint-1
else:
first = midpoint+1

return found

testlist = [0, 1, 2, 8, 13, 17, 19, 32, 42,]
19	print(binarySearch(testlist, 3))
20	print(binarySearch(testlist, 13))``````
``````def sequentialSearch(alist, item):
'''
Function: sequentialSearch
Description: Sequential search on list
Input: List
Output: Tuple of boolean, index
Usage: SequentialSearch(list, item)
Notes: Does not edit list in place
'''
pos = 0
found = False

if alist[pos] == item:
found = True
else:
pos = pos+1

return (found, pos)

testlist = [1, 2, 32, 8, 17, 19, 42, 13, 0]

print(sequentialSearch(testlist, 3))
print(sequentialSearch(testlist, 13))``````
``````haystack=["Zig","Zag","Wally","Ronald","Bush","Krusty","Charlie","Bush","Bozo"]
b = [ "Zig", "Bush" ]

def find_index(lista, listb):

for needle in listb:
try:
print (lista.index(needle), needle)
except ValueError, value_error:
print (needle,"is not in haystack")

print (find_index(haystack, b))``````
``````haystack=["Zig","Zag","Wally","Ronald","Bush","Bush","Krusty","Charlie","Bush","Bozo"]
b = [ "Zig", "Bush" ]

def find_index(lista, listb):
dicta = dict()

for needle in listb:
try:
#print (lista.index(needle), needle)
if needle not in dicta:
dicta[needle] = []
dicta[needle].append(lista.index(needle))
else:
dicta[needle].append(lista.index(needle))
except ValueError:
print (needle,"is not in haystack")
return dicta

print (find_index(haystack, b))``````
``````Functions that search for a specific element in a list, and return its index.
1. binarySearch         = Binary search on array (fastest)
2. SequentialSearch     = Sequential search on array (slowest)
3. index_search         = Sequential search, returns indices of match
4. dict_index_search    = Sequential search, stores matches in dictionary``````