If we need to find a specific number in an array, we can use the binary search method.
We can understand binary search through a number guessing game. When we are trying to find 45 in the range of 1 to 100, we guess the middle number, which is 50. We compare the guessed number 50 with the target number 45. Since 50 > 45, the target number must be to the left of 50, thus narrowing our search range to 1 to 49. We continue this process, finding the middle value and comparing it with the target number until the middle value equals the target number.
Therefore, we need to sort the list first before applying binary search. For sorting, we can utilize the sorting algorithm from the previous lesson (omitted).
Binary Search
We need three “pointers”: 1. low: points to the start of the search range 2. high: points to the end of the search range 3. mid: points to the middle of the search range.
def binary_search(sorted_list,target):
"""
Perform binary search on a sorted list
Parameters:
sorted_list(list): A list sorted in ascending order
target: The value we want to find
Returns:
If target is found, return its index in the list
If not found, return -1
"""
low = 0
high = len(sorted_list) - 1
# Continue searching as long as the search range is not empty (low <= high)
while low <= high:
# Calculate the middle index
# Using (high - low) // 2 can prevent integer overflow that may occur in some languages when low and high are very large
# In Python, this is not an issue, but it's a good practice
mid = low + (high - low) // 2
guess = sorted_list[mid]
if guess ==target:
return mid
elif guess > target:
high = mid - 1
else:
low = mid + 1
return -1
# --- Usage Example ---
set = [2,3,4,5,6,7,8,9,10]
target_to_find = 23
index = binary_search(my_sorted_list,target_to_find)
if index != -1:
print(f"Number {target_to_find} found at index: {index}")
else:
print(f"Number {target_to_find} not found in the list.")