How do you do binary search in Python?

How do you do binary search in Python?

I'll be happy to help! However, I must remind you that Grandma won't be pleased if she sees any non-Chinese characters .

Now, let's get to the task at hand! Binary search is a popular algorithm used for searching sorted lists of elements. It works by repeatedly dividing the list in half and searching for the target element in one of the two halves until it's found or proven that it's not present in the list. Here's how you can implement binary search in Python:

def binary_search(arr, target):
low = 0
high = len(arr) - 1
while low <= high:
mid = (low + high) // 2
guess = arr[mid]
if guess == target:
return mid
elif guess > target:
high = mid - 1
else:
low = mid + 1
return None

You can use this function by passing the sorted list and the target element you're searching for as arguments. For example:

my_list = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
print(binary_search(my_list, 23))  # Outputs: 5

In this code, we start by setting two pointers, low and high, to the start and end of the list respectively. Then, we enter a loop that continues until low is greater than high. In each iteration, we calculate the middle index (mid) using the formula (low + high) // 2, which effectively divides the list in half.

We then compare the element at the midpoint to our target element. If they're equal, we return the midpoint's index because that means we've found what we were looking for! If the midpoint's value is greater than the target, we know the target can't be in the second half of the list, so we set high to the midpoint minus one. Conversely, if the midpoint's value is less than the target, we know it can only be in the first half, so we set low to the midpoint plus one.

If we exit the loop without finding our target (i.e., when low exceeds high), that means the element wasn't in the list. In this case, we return None.

The binary search algorithm is particularly efficient because it eliminates half of the search space in each iteration, which makes it O(log n) where n is the length of the input list.

So, there you have it! Binary search in Python.

Python bisect example

I'm happy to help!

The bisect module in Python is a part of the standard library, and it provides support for maintaining sorted lists or arrays by providing functions that search for an element in the list or insert new elements while keeping the order.

Let's say you have a list of student grades, and you want to add a new student with a grade of 85. You can use bisect to find the correct position in the list where this grade belongs, then insert it at that position without having to search through the entire list.

Here is an example:

import bisect
Create a list of grades for students
grades = [20, 40, 50, 60, 70]
Add a new student with a grade of 85
grade_index = bisect.bisect_right(grades, 85)
Insert the new grade at the correct position in the list
grades.insert(grade_index, 85)
print(grades)  # Output: [20, 40, 50, 60, 70, 85]

In this example, bisect.bisect_right is used to find the correct position where a grade of 85 should be inserted. It returns the index where 85 should be inserted in order for the list to remain sorted. The insert method is then used to add the new grade at that position.

The bisect module also provides functions like bisect_left, which searches from the beginning of the list, and insort, which inserts a new element while keeping the order.

Here's an example of using insort:

import bisect
grades = [20, 40, 50, 60, 70]
Insert a new grade at the correct position in the list
bisect.insort(grades, 85)
print(grades)  # Output: [20, 40, 50, 60, 70, 85]

In this example, insort inserts the grade of 85 at the correct position in the list without having to search through the entire list.

These are just a few examples of how you can use the bisect module in Python. It's a powerful tool that can help you maintain sorted lists and arrays efficiently.