Java Compare three String-arrays and use Binarysearch

Question

I have three string arrays at length 9 and I want to see if all of them include the same name. I have to do this in linearithmic time, O(NlogN). My plan is to sort two of the arrays and than use binarysearch to find similar names. My code is like this atm:

import edu.princeton.cs.algs4.*;
import java.util.Arrays;
import java.util.ArrayList;
import java.util.List;

public class Triplicate2_2_21 {

  // arrays.binarysearh
  public static void main(String[] args) {
    //Strengir sem innihalda 9 nöfn. Sumir innihalda sama nafnið.
    //Nöfn sem eru eins í öllum 3 listunum eru Hulda og Ingi.
    String[] name1 = {"Helgi", "Arnar", "Hulda", "Hrefna", "Ingi", "Marta",
                    "Svavar", "Ester", "Valur"};
    String[] name2 = {"Oddur", "Birgitta", "Hulda", "Ingi", "Selma", "Svavar",
                    "Sylvia", "Unnar", "Hrefna"};
    String[] name3 = {"Elfa", "Jan", "Hulda", "Hrund", "Ingi", "Marta",
                    "Angela", "Sturla", "Valur"};

    Arrays.sort(name2);
    Arrays.sort(name3);

    for(int i = 0; i < name1.length; i++) {
        if((Arrays.binarySearch(name2,name1[i])).compareTo(Arrays.binarySearch(name3,name1[i])) < 0 ) {
          StdOut.println(name1[i]);
          break;
        }}}}

I just want to print out the first triplicate I find, that´s why I do break. This code example is not working and I can´t figure out how to implement this idea further more. So, I´m here to seek out for your help to finish this.

P.s. this is a homework and the question is from the book Introduction to Algorithms, 4th edition, and sounds like this:

"Triplicates. Given three lists of N names each, devise a linearithmic algorithm to determine if there is any name common to all three lists, and if so, return the first".

One thing to bear in mind is that nlog(n) is strictly slower than 3n, so just doing a linear search is much faster than sorting and then binary searching. So if you didn't opt for that because this is homework, please make sure to make that clear in your post and explain what you have to do vs. what you did around that yourself. Also as @RealSkeptic points out: are you sure you've been asked to implement nlog(n) rather than log(n)? — Mike 'Pomax' Kamermans
– Mike 'Pomax' Kamermans, Commented Feb 5, 2020 at 15:15
I'm not sure compareTo is what you need here. With your approach, I'd probably go for binarySearch(..) >= 0 && binarySearch(..) >= 0, which also short circuits if the first condition isn't met. — sp00m
– sp00m, Commented Feb 5, 2020 at 15:16
@Mike How do you search in 3N that all three arrays contain an arbitrary common element? I see at least N squared in the naive approach. — RealSkeptic
– RealSkeptic, Commented Feb 5, 2020 at 15:24
That's not what I'm reading in the question. Their description is "I want to see if all of them include the same name", which is not the same as "I want to see if they share at least one element". So if they meant the latter, they'll have to update their post to be more precise about what they really need to do. As the first description, there is no iteration over the first list, you just pick an element, and then check if it's in the other two or not. The result is a true or false, with linear runtime. The second description yields element(s), with quadratic time if implemented naively — Mike 'Pomax' Kamermans
– Mike 'Pomax' Kamermans, Commented Feb 5, 2020 at 15:26
Thank you for your answers. I edited the post a little bit. I added the question from the book and I also meant it should be linearithmic not logarithmic sry my bad. — Grétar Már
– Grétar Már, Commented Feb 5, 2020 at 15:36

user10871691 · Accepted Answer · 2020-02-05 15:27:31Z

2

Arrays.binarySearch does return an int, therefore there is no compareTo method. Your code doesn't compile.

To fix it, change the conditional part like this:

if (Arrays.binarySearch(name2, name1[i]) > -1 && Arrays.binarySearch(name3, name1[i]) > -1) {
                System.out.println(name1[i]);
                break;
            }
        }

to catch the case when both searches signal a find.

answered Feb 5, 2020 at 15:27

user10871691

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

1 Comment

Grétar Már Over a year ago

Thank you for your answer, my code is working fine now.

Collectives™ on Stack Overflow

Java Compare three String-arrays and use Binarysearch

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related