Question One Explain how we can apply Binary Search algorithm either directly or
ID: 3701916 • Letter: Q
Question
Question One
Explain how we can apply Binary Search algorithm either directly or indirectly in the following cases:
A- Array1 is an array of sorted integers numbers:
(You must choose an element to show the steps)
Array1:
1
5
7
13
16
22
38
55
70
90
B- Array2 is an array of unsorted integers numbers:
(You can choose an element to show the steps)
Array2:
300
20
121
30
110
25
122
200
250
20
C- Array3 is an array of Strings:
The order of sorting is alphabetical (e.g. “AA” before “BC” and “AA” before “AB”).
(You can choose an element to show the steps)
Array3:
“AA”
“AB”
“BA”
“BC”
“CN”
“FA”
“KF”
“LZ”
“MN”
“ZN”
Question Two
A-Describe the linked list data structure and the use of list iterators.
B- Why iterators is not needed with arrays?
Question Three
By using a linkedlist, write a function removeEvens that will remove any even number that will come after an even number in the list. For explanation, you can see the given examples:
List List after call to removeEvens(list):
(6 2 5 2 8 4 3) (6 5 2 3)
(4 2 5 1) (4 5 1)
() ()
(5 3 7) (5 3 7)
(2 6 4) (2)
public static void removeEvens(LinkedList list) {
}
Array1:
1
5
7
13
16
22
38
55
70
90
Explanation / Answer
Solution:
The first question is done as per Chegg guidelines, please repost others.
1)
Array1:
1
5
7
13
16
22
38
55
70
90
In the above-given array we can apply binary search simply since the given list is in sorted order, so if we have to search for an element, let's say 70 then we will start searching by below steps:
The Array2 is not in sorted order and there is no point in applying binary search on the unsorted array, it will become the linear search.
and if you are applying after sorting the array, that is even bad, since the worst case complexity of sorting will give us n log n.
in another sense linear search is better option here.
Array3:
This array is also in sorted order of strings so our passed string which is the search key will be passed and the binary search will be applied to search for an element.
I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)
Array1:
1
5
7
13
16
22
38
55
70
90
In the above-given array we can apply binary search simply since the given list is in sorted order, so if we have to search for an element, let's say 70 then we will start searching by below steps:
- First, 70 will be compared with the item in the middle of the array
- which is 16 after comparison since 70 is larger than 16, the right subarray will be called for the further search
- Now again in the right subarray, the comparison will be done with 55 and right subarray will be called.
- now 70 will be compared with 70 and its index will be returned.
The Array2 is not in sorted order and there is no point in applying binary search on the unsorted array, it will become the linear search.
and if you are applying after sorting the array, that is even bad, since the worst case complexity of sorting will give us n log n.
in another sense linear search is better option here.
Array3:
This array is also in sorted order of strings so our passed string which is the search key will be passed and the binary search will be applied to search for an element.
I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.