level: Searching
Questions and Answers List
level questions: Searching
| Question | Answer |
|---|---|
| Whast the time complexity of a linear search | O(n) |
| Whast the time complexity of binary search | O(log n) |
| Whast the time complexity of binary tree search | O(log n) |
| What type of list does linear search perform on | Unordered |
| How does a linear search work | Each item is compared sequentially till the target |
| What is the best loop to impliment a linear search and why | Do while loop Becasue if the first item is the corret item the loop will stop unlike a for loop Howeever they do still both have tjme complexity O(N) |
| What type of list is binary search used on | Ordered |
| Why is binary seach time comoleity what it is | Each search halves the list |
| How does binary search work | A binary search works by looking at the midpoint of a list and determining if the target is higher or lower than the midpoint |
| Pseudo code of how to prgram binary search | Found ← FALSE BottomPointer ← 0 TopPointer ← ArrayofNames.Count - 1 Do Until Found = TRUE or TopPointer < BottomPointer Midpoint = int mid TopPointer, BottomPointer If ArrayofNames(Midpoint) = Target Found = TRUE ElseIf ArrayofNames(Midpoint) > Target TopPointer = Midpoint - 1 ElseIf ArrayofNames(Midpoint) < Target BottomPointer = Midpoint + 1 Loop If Found = TRUE Output "Target found at " + Midpoint Else Output Target not found |
| Is a binary saerh tree the same as bianry search What makes it different | its performed on a binary tree |