Problem 3 In this problem, develop an algorithm to search a key in a sorted array. Given an input array of integers and

[answerhappygod]

Problem 3 In This Problem Develop An Algorithm To Search A Key In A Sorted Array Given An Input Array Of Integers And 1 (64.17 KiB) Viewed 31 times

Problem 3 In This Problem Develop An Algorithm To Search A Key In A Sorted Array Given An Input Array Of Integers And 2 (64.17 KiB) Viewed 31 times

Problem 3 In This Problem Develop An Algorithm To Search A Key In A Sorted Array Given An Input Array Of Integers And 3 (55.7 KiB) Viewed 31 times

Problem 3 In This Problem Develop An Algorithm To Search A Key In A Sorted Array Given An Input Array Of Integers And 4 (30.76 KiB) Viewed 31 times

Problem 3 In this problem, develop an algorithm to search a key in a sorted array. Given an input array of integers and a search key, one general approach to searching the key in the array is to scan the array, comparing each element against the search key, until one element matches the key, or no match is found till the end of the array. In the latter case the algorithm concludes that the key is not in the array. When the input array is sorted, we can search in a more efficient way. Assume the array is sorted in ascending order. The idea is, we retrieve the middle value from the array and compare it against the search key. If the middle value and the search key match, we've found it and the algorithm stops. If not so and the search key is smaller than the middle value, we search the 1" (left) half of the array as the key could not be in the 2nd (right) half (convince yourself this is true!), otherwise -- the search key is larger than the middle value -- we search the 2nd half of the array as the key could not be in the 1st half of the array. In the half sub-array, we repeat the above steps, retrieving the middle key of the sub-array, comparing it against the search key. If they match, we've found it and stop. If they are not same, then go to either first half or second half of the subarray based on the comparison result. The search stops either when a match is found, or there is no subarray to search. In the latter case the algorithm concludes that the key is not in the array. Following figure shows the steps of searching 38 in a sorted array. 0 1 2 4 5 6 7 8 9 10 02 16 23 38 56 72 91 97 Search 38 38>23 take 2 Half 38 72 take 1 half Found 38, Return 6 L=0 02 0 02 0 02 05 1 05 1 05 1 05 08 2 08 1 Half 2 3 12 2 08 Discarded 08 3 4 12 16 3 12 3 12 4 16 4 16 M=5 23 5 23 5 6 38 7 8 9 56 72 91 2 Half L=6 7 38 56 1 Half L=6 M=6 H=7 38 56 M-8 72 8 72 9 91 H = 10 97 2nd Half 10 H=10 97 9 91 97
Develop flowchart for this algorithm o Give pre-condition and post-condition for your algorithm. O O The algorithm takes as input a search key and an array, output "key in arr: YES" or "key in arr: NO" Hint: use loop and two variables, one to store the starting index of the current search subarray and another to store the end of the current search subarray. These variables are often called start, end, low, high, etc. Let's call it L and H. In each iteration we search array from index L to H. Initially L is 0 and H is the last index of the original array. In each iteration of the loop, we get middle index M and middle value. If the search key is smaller than the middle values, search 1st half of the array by setting H to be M-1 (L does not change), otherwise, search the 2nd half by setting L to be M+1 (H does not change). Convince yourself this works correctly. o If the search (sub)array is of even size, the middle index can be either the end of the 1st half or the beginning of the 2nd half (so to be precise, the "middle" element should be called "middle-most" element). . The loop should stop immediately when the key is found. What is the terminating condition of the search loop? Must use loops. You should not use recursions. (We will learn recursion later). o Start your flowchart as shown in the following figure. The algorithm takes as input an array arr and a search key key Save the flowchart as img_search.jpg OOO O start arr[] key Implement the algorithm using JavaScript o Complete the function problem3(), and attach the onclick event to the corresponding button in html.. O Your implementation should match your flowchart. Sample output
49.8 102 103 104 105 function problem3() { 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 var arr=[8, 9, 9, 12, 13, 13, 13, 15, 20, 100, 100, 101, 123, 129, 300, 330, 390, 400, 403, 407]; var r= prompt("enter search key for..."); /* you implementation here */ /* prompt user for key with message "enter search key for .. var L = 0; var H= arr.length - 1; while (L <= H) { } let M = Math.floor((L+H)/2); if (arr[M] == key) 3 r = M; H= M-1; B else if(key < arr[M]) H = M = 1; else L = M + 1; see pdf / document.getElementById("output").innerHTML + "in arr:" + (key? 'yes': 'No');