All Flashcards
What are the differences between Linear Search and Binary Search?
Linear Search: Works on unsorted lists, O(n) time complexity | Binary Search: Requires sorted lists, O(log n) time complexity.
Compare the efficiency of Linear Search and Binary Search on large datasets.
Linear Search: Less efficient, checks each element | Binary Search: More efficient, eliminates half of the data with each step.
What are the memory requirements for Linear Search vs. Binary Search?
Linear Search: Minimal, no extra memory needed | Binary Search: Minimal, no significant extra memory needed.
Compare the implementation complexity of Linear Search and Binary Search.
Linear Search: Simple to implement | Binary Search: More complex to implement due to sorting and halving.
Compare the best-case scenarios for Linear Search and Binary Search.
Linear Search: Target is the first element | Binary Search: Target is the middle element.
Compare the worst-case scenarios for Linear Search and Binary Search.
Linear Search: Target is the last element or not present | Binary Search: Target is not present.
Compare the applicability of Linear Search and Binary Search to unsorted lists.
Linear Search: Applicable to unsorted lists | Binary Search: Not applicable to unsorted lists.
Compare the impact of data size on the performance of Linear Search and Binary Search.
Linear Search: Performance degrades linearly with data size | Binary Search: Performance degrades logarithmically with data size.
Compare the ease of understanding for Linear Search and Binary Search.
Linear Search: Easier to understand | Binary Search: More complex to understand.
Compare the need for preprocessing (sorting) in Linear Search and Binary Search.
Linear Search: No preprocessing needed | Binary Search: Requires preprocessing (sorting).
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
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.