***JAVA*** public class Searching { //------------------------------------------
ID: 3603608 • Letter: #
Question
***JAVA***
public class Searching
{
//-----------------------------------------------------------------
//-----------------------------------------------------------------
public static Comparable linearSearch(Comparable[] list,
Comparable target)
{
int index = 0;
boolean found = false;
while (!found && index < list.length)
{
if (list[index].equals(target))
found = true;
else
index++;
}
if (found)
return list[index];
else
return null;
}
public static Comparable binarySearch(Comparable[] list,
Comparable target)
{
int min=0, max=list.length, mid=0;
boolean found = false;
while (!found && min <= max)
{
mid = (min+max) / 2;
if (list[mid].equals(target))
found = true;
else
if (target.compareTo(list[mid]) < 0)
max = mid-1;
else
min = mid+1;
}
if (found)
return list[mid];
else
return null;
}
}
1. Search this array for the integer 67 using the linear and binary search code as written by Lewis.
0- 10
1- 12
2- 18
3- 22
4- 31
5- 34
6- 40
7- 46
8- 59
9- 67
10- 69
11- 72
12- 82
13- 84
14- 98
2. Now repeat the process using 98.
3. Annotate each program clearly explaining what each line does.
Explanation / Answer
Assuming contents of list are
0- 10
1- 12
2- 18
3- 22
4- 31
5- 34
6- 40
7- 46
8- 59
9- 67
10- 69
11- 72
12- 82
13- 84
14- 98
1)
Using linear search for value 67
loop will start from index = 0 and reach till index = 9, so number of comparision required was 10
Using binary search for value 67
min = 0, max = 14, mid = 7
min = 8, max = 14, mid = 11
min = 8, max = 10, mid = 9
as mid=9 contains 67, number of comparision requried is 3
2) index will start from 0 and will reach till 14, so number of comparision required is 15 using linear search
using binary search
min = 0, max = 14, mid = 7
min = 8, max = 14, mid = 11
min = 12, max = 14, mid = 13
min = 14, max = 14, mid = 14
number of comparision required is 4
3)
public class Searching
{
//-----------------------------------------------------------------
//-----------------------------------------------------------------
public static Comparable linearSearch(Comparable[] list, Comparable target) // function with two arguments
{
int index = 0; //initialise index to 0
boolean found = false; //initialise found to false
while (!found && index < list.length) //continue this loop till found is equal to false and value of index is less than length of list passed to this funciton
{
if (list[index].equals(target)) //compare if elements at position index in the list is equal to our target for which we are searching
found = true; // if yes than state found to true
else
index++; //otherwise increment index by 1
}
if (found) //if found is equal to true, than we have found our target in the list
return list[index]; //return target value
else
return null;
}
public static Comparable binarySearch(Comparable[] list,
Comparable target)
{
int min=0, max=list.length, mid=0;
boolean found = false;
while (!found && min <= max) //continue this loop till found is equal to false and min is less than equal to max
{
mid = (min+max) / 2; //find mid
if (list[mid].equals(target)) //compare if elements at position mid in the list is equal to our target for which we are searching
found = true; // if yes than state found to true
else
if (target.compareTo(list[mid]) < 0) //check if out target is less than elements at mid
max = mid-1; //narrow search to lower half
else
min = mid+1; //narrow search to upper half
}
if (found)
return list[mid];
else
return null;
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.