BINARY SEARCH (PYTHON)

A binary search is an algorithm that is used to search for an element in a sorted list. It works by comparing the element to be searched with the middle element of the list. If the element to be searched is smaller than the middle element, then the algorithm searches the left half of the list. If the element to be searched is greater than the middle element, then the algorithm searches the right half of the list. This process is repeated until the element is found or the list is exhausted.

Here is an example of how to implement a binary search in Python:

def binary_search(arr, x):
  # Set the initial values for the search
  left = 0
  right = len(arr) - 1
  
  # Loop until the element is found or the list is exhausted
  while left <= right:
    # Calculate the middle index of the current search range
    mid = left + (right - left) // 2
    
    # Check if the element is at the middle of the list
    if arr[mid] == x:
      return mid
    
    # If the element is smaller than the middle element, search the left half of the list
    elif arr[mid] > x:
      right = mid - 1
      
    # If the element is greater than the middle element, search the right half of the list
    else:
      left = mid + 1
      
  # If the element is not found, return -1
  return -1

To use this function, you would call it like this:

# Create a sorted list of numbers
arr = [1, 2, 3, 4, 5]

# Search for the number 3 in the list
x = 3

# Call the binary search function
result = binary_search(arr, x)

# Print the result
print(result)

This would print the index of the number 3 in the list (which is 2), or -1 if the number 3 is not in the list.

Here is an example of a binary search algorithm in Python that can be used to search for bicycle tools in alphabetical order:

def binary_search(tools, target):
    # Set the initial values for the search range
    left = 0
    right = len(tools) - 1

    # Keep searching until the search range becomes empty
    while left <= right:
        # Find the middle element of the search range
        mid = (left + right) // 2

        # If the target is alphabetically before the middle element,
        # search the left half of the range
        if target < tools[mid]:
            right = mid - 1
        # If the target is alphabetically after the middle element,
        # search the right half of the range
        elif target > tools[mid]:
            left = mid + 1
        # If the target is equal to the middle element, we have found it
        else:
            return mid

    # If the target is not found, return -1
    return -1

# Example usage:
tools = ["allen wrench", "bike pump", "hex key set", "tire levers", "tire patch kit"]

# Search for the target "tire levers"
target = "tire levers"
result = binary_search(tools, target)

# Print the result
if result == -1:
    print(f"{target} not found in list")
else:
    print(f"{target} found at index {result} in list")

In this example, the binary search function takes two arguments: a list of tools (tools) and the target tool to search for (target). It returns the index of the target tool in the list, or -1 if it is not found.

To perform the search, the function first sets the initial values for the search range to be the whole list of tools. It then enters a loop that continues until the search range becomes empty.

Inside the loop, the function calculates the middle element of the search range. If the target tool is alphabetically before the middle element, the search range is narrowed to the left half of the current range. If the target tool is alphabetically after the middle element, the search range is narrowed to the right half of the current range. If the target tool is equal to the middle element, the search is complete and the function returns the index of the target tool in the list.