Binary search in python using for loop example

Shelley 154 Published: 08/20/2024

Binary search in python using for loop example

I'd be happy to provide an example of binary search in Python using a for loop.

Binary search is a popular algorithm for finding an element in a sorted list or array. The basic idea behind binary search is that we start by looking at the middle element of the list, and then recursively narrow down the search space until we find the target element.

Here's an example of how you can implement binary search using a for loop in Python:

def binary_search(arr, target):

low = 0


high = len(arr) - 1


for i in range(len(arr)):


mid = (low + high) // 2


if arr[mid] == target:


return mid


elif arr[mid] < target:


low = mid + 1


else:


high = mid - 1


return -1  # not found

Example usage:

arr = [1, 3, 4, 6, 8, 12, 15]


target = 8


result = binary_search(arr, target)


if result != -1:


print(f"Element {target} found at index {result}.")


else:


print(f"Element {target} not found in the list.")

Let's break down how this code works:

We initialize two variables low and high to represent the search space. Initially, low is set to 0 (the start of the array) and high is set to the length of the array minus 1 (the end of the array). The for loop iterates over each element in the array. For each iteration, we calculate the midpoint of the search space using the formula (low + high) // 2. This is the element that we'll compare to our target element. If the midpoint element is equal to the target element, we return its index (since we've found the target). If the midpoint element is less than the target element, we know that the target must be in the upper half of the search space, so we update low to be one more than the midpoint. Otherwise, if the midpoint element is greater than the target element, we know that the target must be in the lower half of the search space, so we update high to be one less than the midpoint. The loop continues until we find the target element or determine that it's not present in the list.

In this example, if you call binary_search(arr, 8), the function will return the index 4, since the element 8 is located at that position in the array. If you call binary_search(arr, 16) (which is not present in the array), the function will return -1, indicating that the target element was not found.

Note that while this implementation uses a for loop, it's actually less efficient than a recursive or iterative binary search using a single variable and updating bounds. However, it can be useful for illustrating how binary search works at a high level.

Binary search in Python w3schools

I'm happy to help!

Binary Search:

What is Binary Search?

Binary search, also known as binary chop, is an algorithm that finds an element in a sorted array by repeatedly dividing the search interval in half and searching for the target value in one of the two halves.

Why Use Binary Search?

Binary search has several advantages over other search algorithms:

Efficient: Binary search is particularly useful when dealing with large datasets, as it reduces the number of comparisons needed to find an element. Fast: The average time complexity of binary search is O(log n), which means that for a dataset of size n, it takes approximately log2n operations to find an element.

How Does Binary Search Work?

Here's how you can implement binary search in Python using the w3schools example:

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

Example Usage:

You can use this function to search for a specific element in the array:

arr = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]

target = 23


result = binary_search(arr, target)


if result is not None:


print(f"Target found at index {result}.")


else:


print("Target not found.")

Conclusion:

Binary search is an efficient algorithm for searching a sorted array. It's particularly useful when dealing with large datasets or real-time applications where fast response time is crucial. In this example, we've implemented binary search in Python and demonstrated its usage.

Related Articles