Revise later
SpaceTo flip
If confident
All Flashcards
What are the steps of Binary Search?
1. 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?
1. 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?
1. 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?
1. 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?
1. 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?
1. 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?
1. 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?
1. 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?
1. 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?
1. Return the index of the middle element. 2. Terminate the search. 3. Optionally, perform additional actions (e.g., print a message).
What is Binary Search?
A search algorithm that repeatedly divides a sorted list in half to find a target value.
What is Linear Search?
A search algorithm that checks each item in a list sequentially until the target value is found.
What is Time Complexity?
A measure of the amount of time taken by an algorithm to run as a function of the input size.
What is O(n) Time Complexity?
Linear time complexity, where the time taken increases linearly with the input size.
What is O(log n) Time Complexity?
Logarithmic time complexity, where the time taken increases logarithmically with the input size.
What does 'sorted list' mean?
A list where elements are arranged in a specific order (ascending or descending).
Define 'search space'.
The portion of the data structure that is being examined by a search algorithm.
What is an algorithm?
A step-by-step procedure for solving a problem.
What is a Data Structure?
A way of organizing and storing data.
What is the 'middle element' in binary search?
The element located at the midpoint of the current search space.
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.