Challenge 1
- Algorithms course
- Beginner
- Lesson 77/80
- 4 min
Write an algorithm to find the largest element in an array.
Challenge 1: Search and sort
In this challenge you will combine linear search and bubble sort. First sort the array, then find the target with binary search.
Array: [5, 2, 8, 1, 9]. Target: 8. Sorted: [1, 2, 5, 8, 9]. Find 8's index with binary search.
Practice Sort and search
Write sort_and_search(arr, target). Sort with bubble sort, then find with binary search. Print 3 with print(sort_and_search([5,2,8,1,9], 8)).
Starter code
def sort_and_search(arr, target):
# Sort and searchSample solution
def sort_and_search(arr, target):
# Sort and search
for i in range(len(arr)):
for j in range(len(arr) - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
left = 0
right = len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
print(sort_and_search([5, 2, 8, 1, 9], 8))Expected output
3
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 What is 8's index in sorted [1,2,5,8,9]?
- 4
- 3
- 2 Correct answer
- 1
Explanation: 8's index is 3.
2 Binary search
Question
Binary search on a sorted array requires ____.
Answer
Binary search on a sorted array requires a sorted array.Explanation: a sorted array is right.
3 Challenge 1: match the terms
| Term | Meaning |
|---|---|
bubble sort |
Sorts |
binary search |
Finds |
O(n^2) |
Sorting |
O(log n) |
Search |