binary search in python code example

Example 1: 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

Example 2: 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 3: 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)

Example 4: binary search python

def binary_search(records:list, search_target, key=None):
    """Returns {'index':search_target_index, 'records':sorted_records_list} of
       the search query else False.
    
    Uses binary search algorithm. Searches both [1,2,3,...] & [{},{},{},...].
    
    The later uses the "key" parameter else key=None.
    For example:
    r=binary_search(records=my_recs, search_target=4377017701570, key="orderId")
    record=r['records'][r['index']]
    ~~~
    l=binary_search(records=my_list, search_target='foo')
    item=l['records'][l['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
      # conditinal inequalities & the arithmitic.
    # sort_records = f'records.sort(key=lambda record: record["{key}"], reverse=False)' # alters 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:
        sort_records = sort_records.replace(f'key=lambda record: record["{key}"], ','')
        reference_target = reference_target.replace(f'["{key}"]','')

    # eval(sort_records) # alters 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.

            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

Example 5: binary search in python

def binary_search(group, suspect):
  group.sort()
  midpoint = len(group)//2
  while(True):
    if(group[midpoint] == suspect):
      return midpoint
    if(suspect > group[midpoint]):
            group = group[midpoint]
    if(suspect < group[midpoint]):
      group = group[0: midpoint]
    midpoint = (len(group)//2)

Example 6: code of binary search in python

def binary_search(mylist,low,k,key):
    high = k - 1
    mid = (low + high)//2
    
    if mylist[mid]==key:
        return mid
    elif key > mylist[mid]:
        return binary_search(mylist,mid + 1,k ,key)
    else:
        return binary_search(mylist,0,mid, key)
low = 0
k = int(input("Enter total amount of elements in k : "))
mylist = [int(input()) for x in range(k)]
key = int(input("Which element do  we have to find: "))
print(binary_search(mylist,low,k,key))