Convert the following from english to pseudocode. 1. Insertion into an ordered a
ID: 3708775 • Letter: C
Question
Convert the following from english to pseudocode.
1. Insertion into an ordered array of integers with duplicates allowed.
2. Binary search on an ordered array of integers with no duplicates allowed. Your algorithm should return the index of the desired integer or -1 if not found. Your algorithm must implement the binary search algorithm given in english:
Binary search in an ordered array with no duplicates allowed in english.
1. Set the lower bound to the index of the first element in the array.
2. Set the upper bound to the index of the last element in the array.
3. Repeat the following until element found/not found:
a. find the index halfway between the lower and upper bounds
b. if the element at that index is equal to the key, return that element
c. determine whether the key lies to the left or right of the middle index element and use that sub-array in the remaining steps
d. if there are no elements in the chosen sub-array, return that the element was not found
e. Set the lower bound to the index of the first element in the sub-array.
f. Set the upper bound to the index of the last element in the sub-array.
Explanation / Answer
1. Insertion into an ordered array of integers with duplicates allowed.
The pseudocode is as follows:
//Inserts a key in arr[] of given capacity. n is current
// size of arr[]. This function returns n+1 if insertion
// is successful, else n.
def insertOrdered( int arr[], int n.int key, int capacity)
if n is greater than or equal to capacity:
return n;
integer i = n
while i greater than or equal to 0 and arr[i] greater than key:
arr[i+1]=arr[i]
end while
arr[i+1]=key
return n+1;
end
2. Binary search on an ordered array of integers with no duplicates allowed. Your algorithm should return the index of the desired integer or -1 if not found. Your algorithm must implement the binary search algorithm given in english:
The pseudo code is as follows: