Searches & Sorts:

What are search algorithms commonly used for?

Search algorithms use a distinct formula to search through arrays.

What is a binary search?

A 'divide and conquer' mechanism that only works on sorted data.

When will a binary search return -1?

When the searched element is not present in the array.

What is the worst-case scenario for a binary search?

The key is not in the array or is at an endpoint.

How is the number of comparisons calculated in the worst case for binary search?

Round n up to the next power of 2 and take the exponent.

What does a sequential search do?

It starts at the first element and compares the key to each element in turn.

What is the best case for a sequential search?

The key is found in the first slot of the array.

What is a selection sort?

A search-and-swap algorithm that finds and exchanges the smallest element with the first element.

What is the efficiency of selection sort for large n?

Inefficient for large n.

What do insertion sorts compare?

They compare the first two elements and insert the second value into the correct position.

What is the worst-case scenario for an insertion sort?

When the array is initially sorted in reverse order.

What is merge sort?

A divide and conquer algorithm that employs recursion.

What is the disadvantage of merge sort?

It requires a temporary array as large as the original array.

How does merge sort handle the initial ordering of elements?

It is not affected; the best, worst, and average cases have similar run times.