1) Show me the steps for a binary search of the following sorted array for the n
ID: 3749060 • Letter: 1
Question
1) Show me the steps for a binary search of the following sorted array for the number 15. 1 8 10 14 16 26 50 2) Using bubble sort, sort the following array from lowest to highest. 100 75 25 50 3) Using selection sort, sort the above array from lowest to highest. 4) Assume you start with an unsorted array. Should you sort then search? Or just use a linear search? Why? 5) Describe, in a flow-chart or pseudocode, how you would search for a word through a sorted array of characters. Order: upper case, lower case, numbers.Explanation / Answer
1)Binary search is the best sorting algorithm which is based on the divide and conquer strategy with the time complexity O(logn) .The binary search is performed on the sorted array this is the prerequisite in order to apply the binary search that is the array should be sorted.The binary search first compares the given element with the middle element of the array,if the given element is greater than the middle element then search will be done on the right sub array that is on the elements that are right to the middle element else on the left sub part.Again the subarray is considered as the array and this procedure is repeated on the array until we find the element or the until all the elements are completed and when the middle element becomes itself
Given elements are
1 8 10 14 16 26 50
Here total elements is 7
Middle element is 7/2=3
Here we have to search for 15,middle element is 10
15>10 so we have to search in right sub array which contains 4 elements
middle element is 4/2 that is element 16
as 15<16 we have search in 14 16 subarray ,in this subarray the middle element is 2/2=1
14<15 and 16>15 therefore 15 is not in the array.
2)In bubble sort at each iteration highest element will bubbled at the end of each iteration starting from the initial element.We will comapare the two adjacent element and we will swap if they are not in the relative order that is the smallest on the left side and largest element on the right side
100 75 25 50 0
we will compare 100 and 75 ,100>75 we will swap
75 100 25 50 0
100>25 we will swap
75 25 100 50 0
100>50 we will swap
75 25 50 100 0
100>0 we will swap
at the end of first iteration
75 25 50 0 100
Second iteration we done it upto 4 elements only as the highest number in the array is bubbled out
75>25 we will swap
25 75 50 0 100
75>50 we will swap
25 50 75 0 100
75>0 we will swap
25 50 0 75 100
at the end of second iteration 25 50 0 75 100
third iteration we done it upto 3 elements only as the2 highest numbers in the array is bubbled out
25<50 we didnt swap
50>0 we will swap
25 0 50 75 100
at the end of third iteration 25 0 50 75 100
25>0 we will swap
0 25 50 75 100
As the elements is in increasing order we will stop here
3)Selection is one of the sorting algorithm which requires minimum number of swaps that is it doesnt take more than O(n) swaps.The time complexity of selection sort is O(n2 ). In selection sort we will find the minimum element in every iteration by comapring all the elements and we will place the minimum element at the starting of the array .The given elements are
100 75 25 50 0
The selction sort will contain 2 subparts one is sorted and other is not sorted we will pick minimum elemnet from unsorted and add it to sorted
The first position where 100 is stored presently, we search the whole list and find that 0 is the lowest value and we will swap 100 and 0 .Now the array is
0 75 25 50 100
Now the second position where 75 is stored presently, we search the whole list from 75 and find that 25 is the lowest value and we will swap 25 and 75.
0 25 75 50 100
Now the third position where 75 is stored presently, we search the whole list from 75 and find that 50 is the lowest value and we will swap 50 and 75.
0 25 50 75 100
Final list is 0 25 50 75 100
4)There are two types of search algorithms they are Linear search and binary search.
In linear search we will search for the element in a sequential manner which requires the O(n) time .
for binary search we will do it in O(logn) time but the array should be in sorted order.If the array is not sorted then you have to search for the element by iteration ,linear search . There is no better way than O(n).Although if you're searching multiple times, it would be better if you sort ( O(nlogn)) it and then use binary search to make the following searches fast in O(log(n)).
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.