Example 1: binary search in python
def binary_search(item_list,item):
first = 0
last = len(item_list)-1
found = False
while( first<=last and not found):
mid = (first + last)//2
if item_list[mid] == item :
found = True
else:
if item < item_list[mid]:
last = mid - 1
else:
first = mid + 1
return found
Example 2: binary search python
def binary_search(records:list, search_target, key=None, index=None):
"""Returns {'index':search_target_index, 'records':sorted_records_list} of
the search query else False.
Uses binary search algorithm.
Searches [foo,grok,spam,...], {x,y,z,...}, [{},{},{},...], or [(),(),(),...]
[foo,grok,spam,...] uses key=None, index=None.
{x,y,z,...} uses key=None, index=None.
[{},{},{},...] uses the "key" parameter else key=None.
[(),(),(),...] uses the "index" parameter else index=None.
Examples:
[{},{},{},...]
r=binary_search(records=my_recs, search_target=4377017701570, key="orderId")
record=r['records'][r['index']]
~~~
[foo,grok,spam,...]
l=binary_search(records=my_list, search_target='foo')
item=l['records'][l['index']]
~~~
bs_set = {10,2,5,8,9,3,6,7,4,1}
result=binary_search(records=bs_set, search_target=5, key=None, index=None)
result={'index': 4, 'records': [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]}.
~~~
[(),(),(),...]
my_reco_tups=[('hello',43770,'world',17701570),('bye',843,'world',17701570)]**
rt=binary_search(records=my_reco_tups,search_target=17701570,key=None,index=3)
target_tup=rt['records'][rt['index']]
**Note: rt['index'] represents first match. bc sorted, next index also matches, if any.
i.e. search_target == rt['records'][rt['index']+1][index]
Important Note:
Because the "records" parameter is a mutable of type list, the code in the
function will mutate and operate on the original argument object in memory
and not a copy of it. If you do not want the original object altered, pass
a copy and not the original object. The index returned corresponds to the
mutated/sorted object.
For example:
bs_list = [10,2,5,8,9,3,6,7,4,1]
bs_list_copy = bs_list.copy()
l = binary_search(records=bs_list_copy, search_target=5)
5 == l['records'][l['index']]
5 == bs_list_copy[l['index']]
bs_list== [10,2,5,8,9,3,6,7,4,1]
bs_list_copy == [1,2,3,4,5,6,7,8,9,10]
Design choice:
Used "doesn't alter list" to eliminate mutation issue. Thus, "Important Note"
doesn't apply for this implementation.
Use "alters list" if you don't mind making a copy of the original list or if
you don't mind altering the original list; "Important Note" applies here.
"""
lower_bound = 0
upper_bound = len(records)-1
"""List MUST be sorted in ascending order, due to the
conditional inequalities & the arithmitic."""
sort_records = f'sorted(records,key=lambda record: record["{key}"],reverse=False)'
reference_target = f'records[mid_index]["{key}"]'
if (key==None and index==None):
sort_records = sort_records.replace(f'key=lambda record: record["{key}"],','')
reference_target = reference_target.replace(f'["{key}"]','')
elif (key!=None and index==None):
pass
elif (key==None and index!=None):
sort_records = sort_records.replace(f'["{key}"],',f'[{index}],')
reference_target = reference_target.replace(f'["{key}"]',f'[{index}]')
elif (key!=None and index!=None):
raise Exception("Both 'key' & 'index' should not have a value simutaneously (other than None).")
records = eval(sort_records)
while lower_bound <= upper_bound:
mid_index = (lower_bound+upper_bound) // 2
if search_target == eval(reference_target):
"""Return records to remove sorting ambiguity;
it has been sorted in ascending order."""
return {'index':mid_index, 'records':records}
elif search_target < eval(reference_target):
upper_bound = mid_index - 1
else:
lower_bound = mid_index + 1
return False