Answers for "binary search python"

iterative binary search python

def binary_search(a, key):
	low = 0
	high = len(a) - 1
	while low < high:
		mid = (low + high) // 2
		if key == a[mid]:
			return True
		elif key < mid:
			high = mid - 1
		else:
			low = mid + 1

	return False

python binary search

def binary_search(arr, item):
	first = 0
	last = len(arr) - 1
	while(first <= last):
		mid = (first + last) // 2
		if arr[mid] == item :
			return True
		elif item < arr[mid]:
			last = mid - 1
		else:
			first = mid + 1	
	return False

binary search python

# This is real binary search
# this algorithm works very good because it is recursive

def binarySearch(arr, min, max, x):
    if max >= min:
        i = int(min + (max - min) / 2) # average
        if arr[i] == x:
            return i
        elif arr[i] < x:
            return binarySearch(arr, i + 1, max, x)
        else:
            return binarySearch(arr, min, i - 1, x)

binary search python

#binary search python
def binaryy(ar, ele):
    low = 0 
    high = len(ar)-1
    if ele not in ar:
        return "Not Found"
    while low <= high:
        mid = (low + high) // 2
        if ar[mid] < ele:
            low = mid + 1
        elif ar[mid] > ele:
            high = mid - 1
        else:
            return mid


ar = [10, 20, 30, 40, 50]
ele = 55
print(binaryy(ar, ele))

python binary search program

#grepper

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

binary search python

def binary_search(records:list, search_target, key=None, index=None, return_multimatch=False):
    """Returns dictionary of {index, duplicates, iter(sorted_records)}.
    
    Searches [foo,grok,spam,...], {x,y,z,...}, [{},{},{},...], or [(),(),(),...]
    l=[10,2,5,8,9,3,6,7,4,2,5,1,7,4,9,2,9]
    >>> binary_search(records=l, search_target=9, return_multimatch=True, key=None, index=None)
        {'index': 14,
         'multimatch_indicies': [13, 14, 15],
         'records': [1, 2, 2, 2, 3, 4, 4, 5, 5, 6, 7, 7, 8, 9, 9, 9, 10]}
	** 'index' represents first match, not necessarily first in sequence.
    
    lt=[('hello',43770,'world',17701570),('bye',843,'world',17701570)]
    rt=binary_search(records=lt, search_target=17701570, key=None, index=3)
    target_tup = list(rt['records'])[rt['index']]
    """
    lower_bound = 0
    upper_bound = len(records)-1
    """List MUST be sorted in ascending order, due to the conditional inequalities & the arithmitic; else use linear search."""
    # sort_records = f'records.sort(key=lambda record: record["{key}"],reverse=False)' # alters OG list
    sort_records = f'sorted(records,key=lambda record: record["{key}"],reverse=False)' # doesn't alter list
    reference_target = f'records[mid_index]["{key}"]'
    if (key==None and index==None): # [1,2,3,...] or {x,y,z,...}
        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 # base case
    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').")
    # eval(sort_records) # alters Original list
    records = eval(sort_records) # doesn't alter list
    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.
            if return_multimatch: # Returns a list of indicies that matches the search_target (i.e. ID duplicates).
                i = mid_index
                h = mid_index-1
                multimatch_indicies=[]
                if (key==None and index!=None): # [(),(),(),...]
                    try:
                        while search_target==records[i][index]: # run forward
                            multimatch_indicies.append(i)
                            i+=1
                    except IndexError:
                        pass
                    try:
                        while search_target==records[h][index] and h>=0: # run backward
                            multimatch_indicies.append(h)
                            h-=1
                    except IndexError:
                        pass        
                    return {'index':mid_index, 'multimatch_indicies':sorted(multimatch_indicies), 'records':iter(records)}
                elif (key==None and index==None): # [1,2,3,...] or {x,y,z,...}
                    try:
                        while search_target==records[i]: # run forward
                            multimatch_indicies.append(i)
                            i+=1
                    except IndexError:
                        pass
                    try:
                        while search_target==records[h] and h>=0: # run backward
                            multimatch_indicies.append(h)
                            h-=1
                    except IndexError:
                        pass         
                    return {'index':mid_index, 'multimatch_indicies':sorted(multimatch_indicies), 'records':iter(records)}
                elif (key!=None and index==None):  # [{},{},{},...]
                    try:
                        while search_target==records[i][key]: # run forward
                            multimatch_indicies.append(i)
                            i+=1
                    except IndexError:
                        pass
                    try:
                        while search_target==records[h][key] and h>=0: # run backward
                            multimatch_indicies.append(h)
                            h-=1
                    except IndexError:
                        pass          
                    return {'index':mid_index, 'multimatch_indicies':sorted(multimatch_indicies), 'records':iter(records)}
            # return True
            return {'index':mid_index, 'records':iter(records)}
        elif search_target < eval(reference_target):
            upper_bound = mid_index - 1
        else:
            lower_bound = mid_index + 1
    return False