binary search python

1def binary_search(arr, item):
2	first = 0
3	last = len(arr) - 1
4	while(first <= last):
5		mid = (first + last) // 2
6		if arr[mid] == item :
7			return True
8		elif item < arr[mid]:
9			last = mid - 1
10		else:
11			first = mid + 1	
12	return False

1def binary_search(a, key):
2	low = 0
3	high = len(a) - 1
4	while low < high:
5		mid = (low + high) // 2
6		if key == a[mid]:
7			return True
8		elif key < mid:
9			high = mid - 1
10		else:
11			low = mid + 1
12
13	return False

1# This is real binary search
2# this algorithm works very good because it is recursive
3
4def binarySearch(arr, min, max, x):
5    if max >= min:
6        i = int(min + (max - min) / 2) # average
7        if arr[i] == x:
8            return i
9        elif arr[i] < x:
10            return binarySearch(arr, i + 1, max, x)
11        else:
12            return binarySearch(arr, min, i - 1, x)
13

1#grepper
2
3def binary_search(item_list,item):
4	first = 0
5	last = len(item_list)-1
6	found = False
7	while( first<=last and not found):
8		mid = (first + last)//2
9		if item_list[mid] == item :
10			found = True
11		else:
12			if item < item_list[mid]:
13				last = mid - 1
14			else:
15				first = mid + 1	
16	return found

1#binary search python
2def binaryy(ar, ele):
3    low = 0 
4    high = len(ar)-1
5    if ele not in ar:
6        return "Not Found"
7    while low <= high:
8        mid = (low + high) // 2
9        if ar[mid] < ele:
10            low = mid + 1
11        elif ar[mid] > ele:
12            high = mid - 1
13        else:
14            return mid
15
16
17ar = [10, 20, 30, 40, 50]
18ele = 55
19print(binaryy(ar, ele))

1def binary_search(records:list, search_target, key=None, index=None, return_multimatch=False):
2    """Returns dictionary of {index, duplicates, iter(sorted_records)}.
3    
4    Searches [foo,grok,spam,...], {x,y,z,...}, [{},{},{},...], or [(),(),(),...]
5    l=[10,2,5,8,9,3,6,7,4,2,5,1,7,4,9,2,9]
6    >>> binary_search(records=l, search_target=9, return_multimatch=True, key=None, index=None)
7        {'index': 14,
8         'multimatch_indicies': [13, 14, 15],
9         'records': [1, 2, 2, 2, 3, 4, 4, 5, 5, 6, 7, 7, 8, 9, 9, 9, 10]}
10	** 'index' represents first match, not necessarily first in sequence.
11    
12    lt=[('hello',43770,'world',17701570),('bye',843,'world',17701570)]
13    rt=binary_search(records=lt, search_target=17701570, key=None, index=3)
14    target_tup = list(rt['records'])[rt['index']]
15    """
16    lower_bound = 0
17    upper_bound = len(records)-1
18    """List MUST be sorted in ascending order, due to the conditional inequalities & the arithmitic; else use linear search."""
19    # sort_records = f'records.sort(key=lambda record: record["{key}"],reverse=False)' # alters OG list
20    sort_records = f'sorted(records,key=lambda record: record["{key}"],reverse=False)' # doesn't alter list
21    reference_target = f'records[mid_index]["{key}"]'
22    if (key==None and index==None): # [1,2,3,...] or {x,y,z,...}
23        sort_records = sort_records.replace(f'key=lambda record: record["{key}"],','')
24        reference_target = reference_target.replace(f'["{key}"]','')
25    elif (key!=None and index==None): # [{},{},{},...]
26        pass # base case
27    elif (key==None and index!=None): # [(),(),(),...]
28        sort_records = sort_records.replace(f'["{key}"],',f'[{index}],')
29        reference_target = reference_target.replace(f'["{key}"]',f'[{index}]')
30    elif (key!=None and index!=None):
31        raise Exception("Both 'key' & 'index' should not have a value simutaneously (other than 'None').")
32    # eval(sort_records) # alters Original list
33    records = eval(sort_records) # doesn't alter list
34    while lower_bound <= upper_bound:
35        mid_index = (lower_bound+upper_bound) // 2
36        if search_target == eval(reference_target): # Return records to remove sorting ambiguity; it has been sorted in ascending order.
37            if return_multimatch: # Returns a list of indicies that matches the search_target (i.e. ID duplicates).
38                i = mid_index
39                h = mid_index-1
40                multimatch_indicies=[]
41                if (key==None and index!=None): # [(),(),(),...]
42                    try:
43                        while search_target==records[i][index]: # run forward
44                            multimatch_indicies.append(i)
45                            i+=1
46                    except IndexError:
47                        pass
48                    try:
49                        while search_target==records[h][index] and h>=0: # run backward
50                            multimatch_indicies.append(h)
51                            h-=1
52                    except IndexError:
53                        pass        
54                    return {'index':mid_index, 'multimatch_indicies':sorted(multimatch_indicies), 'records':iter(records)}
55                elif (key==None and index==None): # [1,2,3,...] or {x,y,z,...}
56                    try:
57                        while search_target==records[i]: # run forward
58                            multimatch_indicies.append(i)
59                            i+=1
60                    except IndexError:
61                        pass
62                    try:
63                        while search_target==records[h] and h>=0: # run backward
64                            multimatch_indicies.append(h)
65                            h-=1
66                    except IndexError:
67                        pass         
68                    return {'index':mid_index, 'multimatch_indicies':sorted(multimatch_indicies), 'records':iter(records)}
69                elif (key!=None and index==None):  # [{},{},{},...]
70                    try:
71                        while search_target==records[i][key]: # run forward
72                            multimatch_indicies.append(i)
73                            i+=1
74                    except IndexError:
75                        pass
76                    try:
77                        while search_target==records[h][key] and h>=0: # run backward
78                            multimatch_indicies.append(h)
79                            h-=1
80                    except IndexError:
81                        pass          
82                    return {'index':mid_index, 'multimatch_indicies':sorted(multimatch_indicies), 'records':iter(records)}
83            # return True
84            return {'index':mid_index, 'records':iter(records)}
85        elif search_target < eval(reference_target):
86            upper_bound = mid_index - 1
87        else:
88            lower_bound = mid_index + 1
89    return False