Removing duplicates from an array without set

Question

                                  EDITED VERSION

I need to remove duplicates from an array for a project. I have seen that people advise using "set", I haven't learned that in my class so I can't use it. I've asked my instructor and he pointed me in a good direction. This is very long but that is only because of the many print statements that I am using to help me understand what the code is doing. (CODE AT BOTTOM). I believe there is a problem with inserting the non duplicate number in the array.

                               HERE IS MY OUTPUT
LB: 0
UB: 10
PROBE: 5
Value of Arrays: 0
randomNumber:42
LB: 6
UB: 10
PROBE: 8
Value of Arrays: 0
randomNumber:42
LB: 9
UB: 10
PROBE: 9
Value of Arrays: 0
randomNumber:42
LB: 10
UB: 10
PROBE: 10
Value of Arrays: 0
randomNumber:42
Return False
42
0
0
0
0
0
0
0
0
0
LB: 0
UB: 10
PROBE: 5
Value of Arrays: 42
randomNumber:75
LB: 6
UB: 10
PROBE: 8
Value of Arrays: 42
randomNumber:75
LB: 9
UB: 10
PROBE: 9
Value of Arrays: 42
randomNumber:75
LB: 10
UB: 10
PROBE: 10
Value of Arrays: 0
randomNumber:75
Return False
42
75
42
42
42
42
42
42
42
42
LB: 0
UB: 10
PROBE: 5
Value of Arrays: 75
randomNumber:74
LB: 0
UB: 4
PROBE: 2
Value of Arrays: 75
randomNumber:74
LB: 0
UB: 1
PROBE: 0
Value of Arrays: 42
randomNumber:74
LB: 1
UB: 1
PROBE: 1
Value of Arrays: 75
randomNumber:74
Return False
42
75
74
75
75
75
75
75
75
75
LB: 0
UB: 10
PROBE: 5
Value of Arrays: 75
randomNumber:100
LB: 6
UB: 10
PROBE: 8
Value of Arrays: 75
randomNumber:100
LB: 9
UB: 10
PROBE: 9
Value of Arrays: 75
randomNumber:100
LB: 10
UB: 10
PROBE: 10
Value of Arrays: 0
randomNumber:100
Return False
42
75
75
100
75
75
75
75
75
75
LB: 0
UB: 10
PROBE: 5
Value of Arrays: 100
randomNumber:68
LB: 0
UB: 4
PROBE: 2
Value of Arrays: 75
randomNumber:68
LB: 0
UB: 1
PROBE: 0
Value of Arrays: 42
randomNumber:68
LB: 1
UB: 1
PROBE: 1
Value of Arrays: 75
randomNumber:68
Return False
42
75
75
100
68
100
100
100
100
100
LB: 0
UB: 10
PROBE: 5
Value of Arrays: 100
randomNumber:7
LB: 0
UB: 4
PROBE: 2
Value of Arrays: 75
randomNumber:7
LB: 0
UB: 1
PROBE: 0
Value of Arrays: 42
randomNumber:7
Return False
42
75
75
75
100
7
100
100
100
100
LB: 0
UB: 10
PROBE: 5
Value of Arrays: 100
randomNumber:29
LB: 0
UB: 4
PROBE: 2
Value of Arrays: 75
randomNumber:29
LB: 0
UB: 1
PROBE: 0
Value of Arrays: 42
randomNumber:29
Return False
42
42
75
75
75
100
29
100
100
100
LB: 0
UB: 10
PROBE: 5
Value of Arrays: 75
randomNumber:39
LB: 0
UB: 4
PROBE: 2
Value of Arrays: 42
randomNumber:39
LB: 0
UB: 1
PROBE: 0
Value of Arrays: 42
randomNumber:39
Return False
42
42
42
75
75
75
100
39
100
100
LB: 0
UB: 10
PROBE: 5
Value of Arrays: 75
randomNumber:74
LB: 0
UB: 4
PROBE: 2
Value of Arrays: 42
randomNumber:74
LB: 3
UB: 4
PROBE: 3
Value of Arrays: 42
randomNumber:74
LB: 4
UB: 4
PROBE: 4
Value of Arrays: 75
randomNumber:74
Return False
42
42
42
42
75
75
75
100
74
100
LB: 0
UB: 10
PROBE: 5
Value of Arrays: 75
randomNumber:42
LB: 0
UB: 4
PROBE: 2
Value of Arrays: 42
randomNumber:42
LB: 0
UB: 10
PROBE: 5
Value of Arrays: 75
randomNumber:67
LB: 0
UB: 4
PROBE: 2
Value of Arrays: 42
randomNumber:67
LB: 3
UB: 4
PROBE: 3
Value of Arrays: 42
randomNumber:67
LB: 4
UB: 4
PROBE: 4
Value of Arrays: 75
randomNumber:67
Return False
42
42
42
42
75
75
75
75
100
67
LB: 0
UB: 10
PROBE: 5
Value of Arrays: 75
randomNumber:30
LB: 0
UB: 4
PROBE: 2
Value of Arrays: 42
randomNumber:30
LB: 0
UB: 1
PROBE: 0
Value of Arrays: 42
randomNumber:30
Return False
42
42
42
42
75
75
75
75
75
100
                               HERE IS MY CODE  

 public class BinarySearch3{
    public static boolean binarySearch(int[] Arrays, int randomNumber){
        int LB = 0;//declare the lower bound
        int UB = 10;//declare the upper bound
        int probe = (LB + UB) / 2;//calculate the probe
        while(LB <= UB){
            System.out.println("LB: " + LB);  
            System.out.println("UB: " + UB); 
            System.out.println("PROBE: " + probe); 
            System.out.println("Value of Arrays: " + Arrays[probe]); 
            System.out.println("randomNumber:" + randomNumber);  
            //if the number is found return true
            if(Arrays[probe] == randomNumber)
                return true;
            // if the probe is less than the number you want to find make LB
            // the probe + 1. Cutting the list in half
            if(Arrays[probe] < randomNumber)
                LB = probe + 1;
            // if the probe is more than the number you want to find make UB
            // the probe - 1. Cutting the list in half
            else if(Arrays[probe] > randomNumber)
                UB = probe - 1;
            probe = (LB + UB) / 2;//recalculate probe
        }
        // the number was not found
        System.out.println("Return False");
        return false;
    }

    public static void main(String [] args){
        int Arrays[] = new int [11];
        //Check the array
        int randomNumber = 0; int d=0 ;
        while(d < Arrays.length){
            sort.sorting(Arrays);
            do{ // loop until randomNumber not found in array

                randomNumber = (int) (Math.random() * 100) + 1;
            } while(binarySearch(Arrays, randomNumber) == true);
            Arrays[d] = randomNumber; 
            d++;
            for(int k = 0; k < Arrays.length-1; k++) {
                System.out.println(Arrays[k]);
            }
        }
    }
}

this if(dup = false) should be if(!dup) or if(dup == false) — Jorge Campos
– Jorge Campos, Commented Nov 21, 2013 at 0:09
See my edited answer. Also use some IDE that allows you to debug your application it will be a lot easier to find theese simple problems. — Jorge Campos
– Jorge Campos, Commented Nov 21, 2013 at 0:33
Your loop is doing 2 things at once: (1) building an array, (2) doing a binary search. These 2 steps can be done independently and will help you track down your problem. Check out my solution. — bcorso
– bcorso, Commented Nov 21, 2013 at 1:44

Jorge Campos · Accepted Answer · 2013-11-21 00:32:10Z

1

One equal sign is to assign a value.

this if(dup = false) should be if(!dup) or if(dup == false)

Another thing in your code is that you create the variable boolean test = true; and you never change it. So in the second iteration it will do nothing, because your while statment is while(!test)

You have to improve your code a bit in order to execute properly.

edited Nov 21, 2013 at 0:32

answered Nov 21, 2013 at 0:10

Jorge Campos

23.8k7 gold badges65 silver badges95 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

bcorso · Accepted Answer · 2013-11-21 01:45:55Z

1

I would suggest making the binary search it's own function, this would separate out the building of the array from the binary search. This make readability and testing much easier and the binary search reusable.

public class work_on_it{
    public static boolean binarySearch(int[] array, int z){
        int LB = 0;//declare the lower bound
        int UB = array.length - 1;//declare the upper bound
        int probe = (LB + UB) / 2;//calculate the probe
        while(LB <= UB){
            //if the number is found return true
            if(array[probe] == z)
                return true;
            // if the probe is less than the number you want to find make LB
            // the probe + 1. Cutting the list in half
            if(array[probe] < z)
                LB = probe + 1;
            // if the probe is more than the number you want to find make UB
            // the probe - 1. Cutting the list in half
            else if(array[probe] > z)
                UB = probe - 1;
            probe = (LB + UB) / 2;//recalculate probe
        }
        // the number was not found
        return false;
    }

    public static void main(String [] args){
        // array length = LENGTH, array values in (1,...,RANGE)
        int LENGTH = 11, RANGE = 50;
        int[] array = new int [LENGTH];
        // fill array with MAX_VALUE. Ensures unassigned elements last after sort.
        Arrays.fill(array, Integer.MAX_VALUE);

        int z = 0, x = 0;
        while(x < array.length){
            Arrays.sort(array);
            do{ // loop until z not found in array
                z = (int) (Math.random() * RANGE) + 1;
            } while(binarySearch(array, z) == true);
            array[x++] = z;  
        }

        for(int i = 0; i < array.length; i++) {
            System.out.println(array[i]);
        }
    }
}

edited Nov 21, 2013 at 1:45

answered Nov 21, 2013 at 0:53

bcorso

47.5k10 gold badges66 silver badges76 bronze badges

9 Comments

Am i a phyco Over a year ago

Thank you, that helped a little bit. It looks like you are finding the duplicates in the array and printing them. I want the program to make an array with no duplicates. Do you know why if I change the true in this (while(binarySearch(array, z) == true);) to false why it gives an infinite loop. These are the changes that I made.

bcorso Over a year ago

I think I don't understand what you are doing, or you didn't understand my code. The code above builds an array of unique random numbers and then prints out the finished array. Did you try running it?

Am i a phyco Over a year ago

Thanks very much for the response I need all the help I can get. I changed the names of Arrays to array. I assume that was just a mistake on the naming. Then there is "array.fill(array,Integer.MAX_VALUE);" That gives me a method call error. Are you hinting for me to make an array fill method.

Am i a phyco Over a year ago

I started changing the code to get it to work because it wouldn't work. I ended up with this new code(see original question) and it's output(see original question).

bcorso Over a year ago

no, Arrays is not a naming mistake. It's a java library "java.utils.Arrays" and it contains useful functions for dealing with arrays like Arrays.sort and Arrays.fill -- incidentally, it even has Arrays.binarySearch. The program above runs if you import the correct libraries

|

StackSmasher · Accepted Answer · 2013-11-21 00:30:45Z

0

I have not gone through the code logic completely, but here are a couple of mistakes I found,

1. if(dup = true) { z = (int)(Math.random() * 10) + 1; }
else if(dup = false) { array[x] = z;
}

Over here, you are assigning the values and not comparing, use '==' for comparison.

2. while(!test) Over here, since test is set to true before, it will never go inside the while as the condition will be evaluated to false

answered Nov 21, 2013 at 0:30

StackSmasher

3891 gold badge3 silver badges6 bronze badges

1 Comment

Am i a phyco Over a year ago

When i add the second i should change "test = false" inside the loop to test = true. Right?

Collectives™ on Stack Overflow

Removing duplicates from an array without set

3 Answers 3

Comments

9 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

9 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related