Explain how we can apply Binary Search algorithm either directly or indirectly i
ID: 3698788 • Letter: E
Question
Explain how we can apply Binary Search algorithm either directly or indirectly in the following cases:
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
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
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”
Array1:
1
5
7
13
16
22
38
55
70
90
Explanation / Answer
Binary search is applied of an array
if it is already sorted. If we want to apply binary search to an unsorted array
the array has to be sorted first
A)
Given array is
1 5 7 13 16 22 38 55 70 90
Since the array is already sorted, binary search can be directly applied to search and element in the sorted array.
Example: choose: 16
So, mid = (0+9)/2 = 4
Since Array1[4] == 16, so it will return True
B)
Given array is
300 20 121 30 110 25 122 200 250 20
Since the array is unsorted, binary search cannot be directly applied. First the array needs to be sorted. After sorting array will be
20 20 25 30 110 121 122 200 250 300
Now the array is sorted and binary search can be directly applied to search an element in array
Now, you can choose any elemets like above and check for that choosen element.
C)
Given array is
AA AB BA BC CN FA LZ MN ZN
Since the array is already sorted, binary search can be directly applied to search and element in the sorted array without changing the array
Example: choose: AB
In first step: mid = (0+7)/2 = 3
Array3[3] = BC , BC > AB
Step 2: mid = (0 + 2)/2 = 1
Array3[1] = AB , found
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.