LINEAR SEARCH : Write a Java program that will perform linear search on an array
ID: 3674519 • Letter: L
Question
LINEAR SEARCH : Write a Java program that will perform linear search on an array. You must use a function called "linear_search" that takes an array and an integer (key) that must be searched for in the array. LINEAR SEARCH : (RECURSIVE**) Write a Java program that will perform linear search on an array. You must use a function called 'linear_search' that takes an array and an integer (key) that must be searched for in the array. BINARY SEARCH (ITERATIVE): Write a Java program that will perform binary search. You must use a function called 'binary_search' that performs binary search on a sorted array of integers using a loop (i.e., without the use of recursion). BINARY SEARCH (RECURSIVE): Write a Java program that will perform binary search. You must use a function called 'binary_search' that performs binary search on a sorted array of integers using a recursion.Explanation / Answer
I have implemented all above method in a Class, you can add main method and pass appropraite arguments to methods and test;
public class Search
{
//this is recursive linear search method
public void linear_search(int[] arr, int fIndex, int lIndex, int searchNum)
{
if(fIndex == lIndex)
{
System.out.print("-1");
}
else
{
if(arr[fIndex] == searchNum)
{
System.out.print(fIndex);
}
else
{
linear_search(arr, fIndex+1, lIndex, searchNum);
}
}
}
// this is iterative linear_search method
public static int linear_search(int[] arr, int target)
{
int i = 0;
while (i < arr.length) {
if (arr[i] == target) {
return i;
} // if
++i;
}
return -1;
}
// this is recursive binary search
public static int binary_search(int[] sortedArray, int start, int end, int key) {
if (start < end) {
int mid = start + (end - start) / 2;
if (key < sortedArray[mid]) {
return binary_search(sortedArray, start, mid, key);
} else if (key > sortedArray[mid]) {
return binary_search(sortedArray, mid+1, end , key);
} else {
return mid;
}
}
return -(start + 1);
}
// thsi is iterative bunary search
public static int binary_search(int A[], int key)
{
int l = 0;
int r = A.length-1;
//As long as left index is less than right index
while (l <= r)
{
//Middle element
int m = (l + r) / 2;
//If the search key on the left half
if (key < A[m])
{
//Update right index
r = m - 1;
}
//If the search key on the right half
else if (key > A[m])
{
//Update the left index
l = m + 1;
}
//We found the key
else
{
return m;
}
}
//Key was not found
return -1;
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.