6.2 Searching and Sorting Arrays

• Binary search repeatedly divides the search interval in half to locate the target element, but it requires the array to be sorted
• Linear search has a time complexity of O(n)
• Bubble sort repeatedly swaps adjacent elements if they are in the wrong order
• Steps of the linear search algorithm

  1️⃣ Start at the first element

  2️⃣ Check if the current element matches the target

  3️⃣ If not, move to the next element

  4️⃣ Repeat until the target is found or the end of the array
• Steps of the linear search algorithm

  1️⃣ Start at the first element of the array

  2️⃣ Check if the current element matches the target

  3️⃣ If not, move to the next element

  4️⃣ Repeat steps 2-3 until the target is found or the end of the array is reached
• Binary search is an efficient algorithm for finding a target in a sorted array.
• Binary search has a time complexity of O(log n) for sorted arrays.
• The tradeoff of binary search is that it requires the array to be sorted and is more complex to implement.
• What does sorting in arrays refer to?

  Arranging elements in order
• Binary search has a time complexity of O(log n), making it more efficient for large sorted arrays.
• Linear search requires the array to be sorted.

  False
• Binary search requires the array to be sorted
• Binary search has a time complexity of O(log n
• Bubble Sort is inefficient for large arrays due to its time complexity of O(n^2
• Selection Sort is inefficient for large arrays due to its time complexity of O(n^2
• Selection Sort is more efficient than Bubble Sort for large arrays.

  False
• Steps of Insertion Sort

  1️⃣ Assume the first element is already sorted

  2️⃣ Take the next element

  3️⃣ Insert it into the correct position

  4️⃣ Repeat for each unsorted element
• Linear Search checks each element sequentially until the target is found
• Linear Search finds a target element by sequentially checking each element
• What is the time complexity of Binary Search?

  O(log n)
• Binary search has a time complexity of O(log n), making it faster than linear search for large sorted arrays.


  True
• Binary search repeatedly divides the search interval in half, resulting in a time complexity of O(log n).


  True
• Searching in arrays refers to the process of finding a specific element
• The purpose of searching is to efficiently locate a desired element within an array.


  True
• Linear search requires the array to be sorted.

  False
• Insertion sort builds the final sorted array one element at a time
• Linear search is inefficient for large arrays because it has a time complexity of O(n)
• Linear search requires the array to be sorted to function efficiently.

  False
• Binary search works by repeatedly dividing the search interval in half.

  True
• One disadvantage of binary search is that it requires the array to be sorted.


  True
• Searching in arrays involves finding a specific element within the array.


  True
• Bubble sort repeatedly swaps adjacent elements if they are in the wrong order.

  True
• What is the time complexity of linear search?

  O(n)
• In binary search, if the middle element equals the target, the index is returned.


  True
• Binary search is more complex to implement than linear search.


  True
• Bubble Sort performs well for partially sorted arrays.

  False
• Selection Sort is more efficient than Bubble Sort for small arrays.


  True
• What is the time complexity of Bubble Sort?

  O(n^2)
• For which type of data is Insertion Sort efficient?

  Partially sorted data
• What condition is required for Binary Search to work?

  The array must be sorted