Can someone help me with these two programming questions in java? 1).Write a jav
ID: 3569653 • Letter: C
Question
Can someone help me with these two programming questions in java?
1).Write a java program which uses the binary search algorithm to return the location of a number in an array. Returns -1 if not found.
Use this array of numbers
12, 34, 76, 45, 90, 21, 18.
Search for 76.
2). (a). Write down the class structure for a reference implementation of a linked list of integers.
(b) Implement reference linked list of integer with: Insert, delete and print. Test your Test your linked list with the following numbers and operations:
insert 23, 34, 55, 72, 61, 90.
Print list.
Delete 67.
Print list
Explanation / Answer
1)
//java program that implements the binary searach method and
//test the method with elements .
import java.util.Scanner;
class BinarySearchProgram
{
public static void main(String args[])
{
int index;
int size;
int search;
int array[];
Scanner in = new Scanner(System.in);
System.out.println("Enter number of elements");
size = in.nextInt();
array = new int[size];
System.out.println("Enter " + size + " integers");
for (index = 0; index < size; index++)
array[index] = in.nextInt();
System.out.println("Search for ");
search = in.nextInt();
int pos=binarySearch(array, search);
if(pos!=-1)
System.out.println("Element found at "+pos);
else
System.out.println("Element not found");
}
//The method binarySearch that accepts an array and search key
//and returns the position of the search elemenet otherwise
//returns -1
public static int binarySearch(int array[],int search)
{
int first;
int last;
int middle;
int n=array.length;
int position=-1;
first = 0;
last = n - 1;
middle = (first + last)/2;
while( first <= last )
{
if ( array[middle] < search )
first = middle + 1;
else if ( array[middle] == search )
{
position=middle+1;
break;
}
else
last = middle - 1;
middle = (first + last)/2;
}
if ( first > last )
position=-1;
return position;
}
}
Sample output:
Enter number of elements
4
Enter 4 integers
12
23
44
67
Search for
67
Element found at 4
----------------------------------------------------------------------------------------
part b)
1)
//Node class
public class Node
{
Node next;
int data;
// Node constructor
public Node(int _data)
{
next = null;
data = _data;
}
public int getData()
{
return data;
}
public void setData(int _data)
{
data = _data;
}
public Node getNext()
{
return next;
}
public void setNext(Node _next)
{
next = _next;
}
}
--------------------------------------------------------------------------------------------
//LinkedList implementation
public class LinkedList
{
private Node head;
private int element;
public LinkedList()
{
head = new Node(0);
element = 0;
}
//Method to add the data to the list
public void add(int data)
{
Node temp = new Node(data);
Node current = head;
// starting at the head node, crawl to the end of the list
while(current.getNext() != null)
{
current = current.getNext();
}
current.setNext(temp);
}
//Method to remove the element x from the list
public void delete(int x)
{
Node current=head;
if (head.data == x)
head = head.next;
else{
Node temp = head;
while (temp.next != null){
if ((temp.next).data == x)
temp.next = (temp.next).next;
else
temp = temp.next;
}
}
}
//Override the toString method to print the list of elements
public String toString()
{
Node current = head.getNext();
String output = "";
while(current != null)
{
output += current.getData()+" ";
current = current.getNext();
}
return output;
}
}
---------------------------------------------------------------------------------
2)
//Java program to test the LinkedList class
//methods
import java.util.Scanner;
public class Tester
{
public static void main(String[] args) {
Scanner read=new Scanner(System.in);
LinkedList lList=new LinkedList();
lList.add(23);
lList.add(34);
lList.add(55);
lList.add(72);
lList.add(61);
lList.add(90);
System.out.println("Linked List elements");
System.out.println(lList.toString());
System.out.println("Enter element to delete");
int element=read.nextInt();
lList.delete(element);
System.out.println("List after deletion");
System.out.println(lList.toString());
}
}
-----------------------------------------------------
Sample output:
Linked List elements
23 34 55 72 61 90
Enter element to delete
90
List after deletion
23 34 55 72 61
Hope this helps you.