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 are the steps of Binary Search?
- Sort the list. 2. Find the middle element. 3. Compare with the target. 4. Eliminate half the list. 5. Repeat until found or not found.
What are the steps to prepare a list for binary search?
- Ensure the list exists. 2. Populate the list with data. 3. Sort the list in ascending or descending order.
What is the process of narrowing the search space in binary search?
- Compare the target with the middle element. 2. If target is greater, set low to mid + 1. 3. If target is smaller, set high to mid - 1.
What are the steps to determine if a target is 'not found' in binary search?
- Continue dividing and comparing until low > high. 2. If low > high, the target is not in the list. 3. Return a 'not found' indicator (e.g., -1).
What are the initial steps in implementing binary search?
- Get the sorted list. 2. Define the target value. 3. Initialize low to 0 and high to len(list) - 1.
What are the steps to find middle element?
- Sum low and high index. 2. Divide sum by 2. 3. Take the integer part of the result.
What are the steps to compare target with the middle element?
- Check if target equals middle element. 2. If equal, the target is found. 3. If not equal, proceed to eliminate half of the list.
What are the steps to eliminate half of the list?
- If target > middle element, set low = mid + 1. 2. If target < middle element, set high = mid - 1.
What are the steps to repeat the binary search process?
- Check if low <= high. 2. If true, repeat steps to find the middle element and compare. 3. If false, target is not found.
What are the steps to handle the 'target found' scenario?
- Return the index of the middle element. 2. Terminate the search. 3. Optionally, perform additional actions (e.g., print a message).
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