Program 2: Search.java You will implement the following two search methods, also

Question

Program 2: Search.java You will implement the following two search methods, also from scratch (no main method is needed either): // Return index of first occurrence of key in array using linear search // Return -1 if key is not in array public static int linearSearch(int[] array, int key) // Return index of an occurrence of key in sorted array using binary search // Return the insertion index (see Liang) if key is not in array public static int binarySearch(int[] arrayb int key). Like Sort. java, you should attempt to code up your own search implementations using just the written descriptions in Liang. If you encounter difficulties, then refer to the code samples in Liang (p.266 and p.268 in the 10th edition) to help get your code working. Note, searching algorithms are also likely to show up on exams since they too are fundamental in computer science. You must code these from scratch. You may not use the Arrays class. Your methods must handle empty (length-zero) as well as null arrays. Think about what binary's search's insertion index would be for an empty or null array.

Explanation / Answer

Answer:

Methods for Linear search and Binary search:

Linear Search:

class MyCode {
public static int linearSearch(int[] a, int key) {
int n = a.length;
for (int i=0; i<n; i++)
if (a[i] == key)
return i;
return -1;
}

public static void main(String[] args) {
int[] a = { 2, 5, 4, 1, 3 };
System.out.println(linearSearch(a,4));
System.out.println(linearSearch(a,6));
}
}

Binary Search :

class MyCode {
public static int binarySearch(int[] a, int key) {
int lo = 0;
int hi = a.length-1;
while (lo <= hi) {
int i = (lo + hi)/2;
if (a[i] < key)
lo = i + 1;
else if (a[i] > key)
hi = i - 1;
else
// found it!
return i;
}
return -1;
}

public static void main(String[] args) {
int[] a = { 2, 4, 6, 8, 10, 12 };
System.out.println(binarySearch(a,6));
System.out.println(binarySearch(a,7));
}
}

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.