I need help with JAVA program. Please write each following in seperate sheet. Th
ID: 2246479 • Letter: I
Question
I need help with JAVA program. Please write each following in seperate sheet. Thanks
1) Implement the following generic method for linear search. public static > int linearSearch(E[] list, E key) {//please implement the body of method here}
2) Implement the following generic method for binary search public static > int binarySearch(E[] list, E key)
3) Implement the following generic method for binary sort public static> void binarySort(E[] list)
4) implement the following method that returns a new array list which contains non-duplicate elements from the original list. public static E[] removeDuplicates(E[] list)
5) implement the method returns largest element from the two dimensional array public static > E max(E[][] list)
Explanation / Answer
1.
public static int linearSearch(E[] list, E key)
{
int size = list.length;
for(int i=0;i<size;i++)
{
if(list[i] == key)
return i; //returning the index if the key is present in the list
}
return -1; // returning -1 if the key is not present in the list
}
2.
public static int binarySearch(E[] list, E key) {
// Assuming that the list is already sorted. Binary Search works only for sorted lists/arrays.
int start = 0;
int end = list.length - 1;
while (start <= end)
{
int mid = (start + end) / 2; //finding the middle index
if (key == list[mid]) // if the key is found return the index
return mid;
if (key < list[mid]) //if the key is less than the list[mid] then search in the portion left of that mid
end = mid - 1;
else
start = mid + 1; //if the key is greater than the list[mid] then search in the portion right to that mid
}
return -1; // return -1 if the element is not found
}
3.
public static int binarySearch(E[] list, E key,int low, int high)) {
if (low>=high)
{
if(key>list[low])
return low+1;
else
return low;
}
int mid = (low + high)/2;
if(key == list[mid])
return mid+1;
if(key > list[mid])
return binarySearch(E, key, mid+1, high);
return binarySearch(E, key, low, mid-1);
}
//At each iteration, binarySort uses binarySEarch to find a proper/valid location to insert the selected item.
public static void binarySort(E[] list){
int i, loc, j, k;
E selected;
int size=list.length;
for (i = 1; i < size; ++i)
{
j = i - 1;
selected = list[i];
// find index where selected could be inseretd
loc = binarySearch(list, selected, 0, j);
// Move all elements after the loc index to create space at that index
while (j >= loc)
{
list[j+1] = list[j];
j--;
}
list[j+1] = selected;
}
}
4.
public static E[] removeDuplicates(E[] list){
Set<E> set = new HashSet<E>();
int size=list.length;
for (int i = 0; i < size; i++) {
set.add(list[i]);
}
//Since it is a set, the duplicates are not allowed and were removed.
E[] array = new E[set.size()];
int i = 0;
for (Integer num : set) {
array[i++] = num;
}
return array;
}
5.
public static E max(E[][] list)
{
E maximum = list[0][0];
int i = 0;
for(i = 0; i < list.length; i++)
{
for(int j = 0; j < list[0].length; j++)
{
if(list[i][j] > maximum)
maximum = list[i][j];
}
}
return maximum;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.