All Flashcards
What is the key requirement for using binary search?
The list must be sorted.
Why is binary search more efficient than linear search for large, sorted lists?
Binary search eliminates half of the search space with each step, resulting in logarithmic time complexity.
Explain the concept of 'divide and conquer' in relation to binary search.
Binary search uses a divide and conquer approach by repeatedly dividing the search space in half.
What is the worst-case scenario for binary search?
The target element is not in the list, requiring the algorithm to eliminate all possible elements.
What is the best-case scenario for binary search?
The target element is the middle element in the first step.
How does binary search reduce search space?
By comparing the target value to the middle element and eliminating half of the list in each step.
Why is sorting important before applying binary search?
Sorting ensures that elements are in a predictable order, allowing binary search to correctly narrow down the search space.
What is the significance of the middle element in binary search?
It serves as the pivot point for comparison, determining which half of the list to eliminate.
Explain the role of comparisons in binary search.
Comparisons determine whether the target value is greater than, less than, or equal to the middle element, guiding the search.
What is the impact of list size on the performance of binary search?
Binary search performs significantly better on larger lists compared to linear search due to its logarithmic time complexity.
How is Binary Search applied in real-world scenarios?
Searching for a word in a dictionary, finding a contact in a sorted phone book, or locating data in a sorted database index.
Give an example of using Binary Search in a database system.
Finding a specific record by ID in a sorted index of a database table.
How is Binary Search used in version control systems?
Identifying the commit where a bug was introduced using a process similar to binary search (bisecting).
How is Binary Search applied in searching for a value in a sorted array?
Efficiently locating a specific number in a sorted array of integers or floating-point numbers.
How is Binary Search used in searching for a file on a sorted file system?
Quickly finding a file by name in a sorted directory structure.
How is Binary Search utilized in finding a specific entry in a sorted configuration file?
Efficiently locating a configuration setting in a sorted configuration file.
How is Binary Search applied in finding a specific page in a sorted index of a book?
Quickly locating a page number in a sorted index of a book.
How is Binary Search used in searching for a value within a specific range?
Efficiently finding a value that falls within a specified range in a sorted dataset.
How is Binary Search applied in searching for a specific item in a sorted inventory list?
Quickly locating an item by its unique identifier in a sorted inventory list.
How is Binary Search used in searching for a specific record in a sorted log file?
Efficiently finding a log entry by timestamp in a sorted log file.
What does the following code output?
python
list = [2, 5, 7, 8, 11, 12]
target = 13
low = 0
high = len(list) - 1
while low <= high:
mid = (low + high) // 2
if list[mid] == target:
print("Found")
break
elif list[mid] < target:
low = mid + 1
else:
high = mid - 1
else:
print("Not Found")
Not Found
What does the following code output?
python
list = [2, 5, 7, 8, 11, 12]
target = 8
low = 0
high = len(list) - 1
while low <= high:
mid = (low + high) // 2
if list[mid] == target:
print("Found")
break
elif list[mid] < target:
low = mid + 1
else:
high = mid - 1
else:
print("Not Found")
Found
Identify the error in the following code:
python
def binary_search(list, target):
low = 0
high = len(list) - 1
while low < high:
mid = (low + high) // 2
if list[mid] == target:
return mid
elif list[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
The code will enter an infinite loop if the target is not found because the condition low < high will not become false, and it does not handle the case when low == high. It should be low <= high.
What does the following code output?
python
list = [1, 3, 5, 7, 9]
target = 4
low = 0
high = len(list) - 1
while low <= high:
mid = (low + high) // 2
if list[mid] == target:
print("Found")
break
elif list[mid] < target:
low = mid + 1
else:
high = mid - 1
else:
print("Not Found")
Not Found
What does the following code output?
python
list = [1, 3, 5, 7, 9]
target = 1
low = 0
high = len(list) - 1
while low <= high:
mid = (low + high) // 2
if list[mid] == target:
print("Found")
break
elif list[mid] < target:
low = mid + 1
else:
high = mid - 1
else:
print("Not Found")
Found
Identify the error in the following code:
python
def binary_search(list, target):
low = 0
high = len(list)
while low <= high:
mid = (low + high) // 2
if list[mid] == target:
return mid
elif list[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
IndexError: list index out of range. high = len(list) should be high = len(list) - 1
What does the following code output?
python
list = [1, 2, 3, 4, 5]
target = 6
low = 0
high = len(list) - 1
while low <= high:
mid = (low + high) // 2
if list[mid] == target:
print("Found")
break
elif list[mid] < target:
low = mid + 1
else:
high = mid - 1
else:
print("Not Found")
Not Found
What does the following code output?
python
list = [1, 2, 3, 4, 5]
target = 1
low = 0
high = len(list) - 1
while low <= high:
mid = (low + high) // 2
if list[mid] == target:
print("Found")
break
elif list[mid] < target:
low = mid + 1
else:
high = mid - 1
else:
print("Not Found")
Found
Identify the error in the following code:
python
def binary_search(list, target):
low = 0
high = len(list) - 1
while low < high:
mid = (low + high) // 2
if list[mid] == target:
return mid
elif list[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
The while loop condition low < high should be low <= high to correctly handle the case when the target is the last element.
What does the following code output?
python
list = [1, 5, 9, 13, 17]
target = 9
low = 0
high = len(list) - 1
while low <= high:
mid = (low + high) // 2
if list[mid] == target:
print("Found")
break
elif list[mid] < target:
low = mid + 1
else:
high = mid - 1
else:
print("Not Found")
Found