import java.util.Arrays; public class BinarySearch { // precondition: array a[]
ID: 3558589 • Letter: I
Question
import java.util.Arrays;
public class BinarySearch {
// precondition: array a[] is sorted
public static int rank(int key, int[] a) {
int lo = 0;
int hi = a.length - 1;
while (lo <= hi) {
// Key is in a[lo..hi] or not present.
int mid = lo + (hi - lo) / 2;
if (key < a[mid]) hi = mid - 1;
else if (key > a[mid]) lo = mid + 1;
else return mid;
}
return -1;
}
public static void main(String[] args) {
int[] whitelist = new In(args[0]).readAllInts();
Arrays.sort(whitelist);
In keys = new In(args[1]);
// read key; print if not in whitelist
while (!keys.isEmpty()) {
int key = keys.readInt();
if (rank(key, whitelist) == -1)
StdOut.println(key);
}
}
} // end of BinarySearch
Remove duplicates: Modify the test client in BinarySearch to remove any duplicate keys in the whitelist after the sort
Explanation / Answer
package cheg;
import java.util.Arrays;
import java.util.Scanner;
class BinarySearch {
// precondition: array a[] is sorted
public static int rank(int key, int[] a) {
int lo = 0,i,length=a.length;
int hi = a.length - 1;
while (lo <= hi) {
// Key is in a[lo..hi] or not present.
int mid = lo + (hi - lo) / 2;
if (key < a[mid]) hi = mid - 1;
else if (key > a[mid]) lo = mid + 1;
else {
if(mid>0&&mid<hi)
{
if((a[mid-1]==a[mid])||(a[mid+1]==a[mid]))
{
for(i=mid;i<length-1;i++)
a[i]=a[i+1];
--hi;
--length;
}else
break;
}
else if(mid>0&&mid==hi)
{
if(a[mid-1]==a[mid])
{
for(i=mid;i<length-1;i++)
a[i]=a[i+1];
--hi;
--length;
}
else
break;
}else if(mid<hi&&mid==0)
{
if(a[mid+1]==a[mid])
{
for(i=mid;i<length-1;i++)
a[i]=a[i+1];
--hi;
--length;
}else
break;
}else
break;
}
}
return length;
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n,i,k;
System.out.printf(" Enter the quantity of numbers::");
n = in.nextInt();
int[] whitelist=new int[n];
System.out.printf(" Start entering numbers:: ");
for(i=0;i<n;i++)
{
System.out.printf("Enter::");
whitelist[i]=in.nextInt();
}
Arrays.sort(whitelist);
System.out.printf(" Enter the key::");
k=in.nextInt();
n=rank(k,whitelist);
System.out.printf(""+(n));
System.out.printf(" Modified array after removing duplicates ");
for(i=0;i<n;i++)
System.out.printf(" "+whitelist[i]);
System.out.println(" ");
}
} // end of BinarySearch
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.