(3 pts) If a list is sorted in increasing order, we can search the list using an
ID: 3871048 • Letter: #
Question
(3 pts) If a list is sorted in increasing order, we can search the list using another algorithm called Binary Search. The basic idea is to find the middle element, then if that is not the key, you search either the first half of the list or the second half of the list, depending on the half that could contain the key. The process is repeated iteratively until we either find the key or we run out of elements to examine. Here is an implementation in Python 2. def bsearch (datalist, key): 10index = 0 - hi-index = len (datalist)-1 while loindex datalist[mid]: else: - return None Let datalist - [5, 12, 14, 19, 23, 27, 33, 34, 45, 56, 61019 8409e5 5422Explanation / Answer
You don't need to solve any problem my friend, you just need to observe.
as you might have understood from the class, binary search cuts down the range
into half every time it iterates.
This is what I typed in as array, your watermark has made some numbers unclear
[5, 12, 14, 19, 23, 27, 33, 34, 45, 56, 61, 70, 79, 84, 98]
a. 0 - 14, 0 - 6, 4 - 6, 4 - 4, returns 4
Explanation:
1. Algorithm default is 0, 14 indexes (start and end of array)
2. it checks if one right in the middle is the number we need. No it is not 34 != 23.
3. Now it checks if 23 > 34 no, so we don't need to look at higher indices that
right in the middle, then 6 it is.
4. It searches between 0 and 6 and repeats the above steps are repeated.
b. 0 - 14, 8 - 14, 12 - 14, returns 13
c. 0 - 14, 0 - 6, 0 - 2, 2 - 2, returns None
This is a scenario where the last check is made
and still the number is not found.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.