How can I implement binary search in Substring in function and two values in Comparator?

Question

I have a problem about implementing binary search in substring. In my City object, there is a cityName variable as defined String. I want to enter any substring like "Sha" and it shows the result of "Sha". Except for this, there is a weight variable to sort descend city names. For example, the bigger weight value is at the top and the sort process is based on descending.

How can I do that? How can I add this to the comparater area?

Here is my City Object

public class City implements Serializable{
    private Integer cityWeight;
    private String cityName;
}

Here is my code snippet shown below.

// Not implement Binary Search

public static Integer[] searchByCharacters(List<City> list, String sub) {
        List<Integer> result = new ArrayList<>();
        Collections.sort(list);
        for (int i = 0; i < list.size(); i++) {
            if (list.get(i).getCityName().contains(sub))
                result.add(i);
        }
        return result.stream().toArray(Integer[]::new);
}

I want to implement binary search above the code snippet but it doesn't work.

public static Integer[] searchBySubStringCharacter(List<City> list, String sub) {
        List<Integer> result = new ArrayList<>();

        Comparator<City> comparator = new Comparator<City>() {
            public int compare(City node1, City node2) {
                boolean node1Contains = node1.getCityName().contains(sub);
                boolean node2Contains = node2.getCityName().contains(sub);
                if (node1Contains && !node2Contains) {
                    return 1;
                } else if (!node1Contains && node2Contains ) {
                    return -1;
                } else {
                    return 0;
                }
            }
        };

        Collections.sort(list, comparator);
        for (int i = 0; i < list.size(); i++) {
            int index = Collections.binarySearch(list, new City(sub), comparator);
            if (index >= 0)
                result.add(i);
        }

        return result.stream().toArray(Integer[]::new);
    }

This code shows all city list and the result of binary search. How can I extract all city list from the result?

The existing answers may address your compilation issue but... what is the goal of this method? It looks like you are going to sort the List, then find the index of the first match, then fill an array the size of the List with that value, and return that array. I'm guessing this is not your goal. — vsfDawg
– vsfDawg, Commented Apr 30, 2020 at 11:04

Vikas · Accepted Answer · 2020-05-01 03:10:21Z

1

binarySearch accepts the key to be searched for having type the class of the objects in the list,

public static <T> int binarySearch(List<? extends T> list, T key, Comparator<? super T> c)

So pass City object in binarySearch,

for (int i = 0; i < list.size(); i++) {
     int index = Collections.binarySearch(list, new City(sub), comparator);
     if (index >= 0)
        result.add(i);
}

Also if you are using java8+, you can use lambda for Comparator,

Comparator<City> comparator = (node1, node2) -> {
     boolean node1Contains = node1.getCityName().contains(sub);
     boolean node2Contains = node2.getCityName().contains(sub);
     if (node1Contains && !node2Contains) {
        return 1;
     } else if (!node1Contains && node2Contains ) {
        return -1;
     } else {
        return 0;
     }
};

Update: To sort based on the weight in case of a match you need to use Integer.compare(node2.getCityWeight(), node1.getCityWeight()),

Also iyou can not binarySearch with same comparator as you don't know the weight of the city you are searching. you can use Stream,

public static Integer[] searchBySubStringCharacter(List<City> list, String sub) {
  List<Integer> result = new ArrayList<>();

  Comparator<City> comparator = (node1, node2) -> {
     boolean node1Contains = node1.getCityName().contains(sub);
     boolean node2Contains = node2.getCityName().contains(sub);
     if (node1Contains && !node2Contains) {
        return 1;
     } else if (!node1Contains && node2Contains ) {
        return -1;
     } else {
        return Integer.compare(node2.getCityWeight(), node1.getCityWeight());
     }
  };
  Collections.sort(list, comparator);

  return IntStream.rangeClosed(0, list.size() - 1)
          .filter(i -> list.get(i).getCityName().contains(sub))
          .boxed()
          .toArray(Integer[]::new);
}

edited May 1, 2020 at 3:10

answered Apr 30, 2020 at 10:53

Vikas

7,2214 gold badges30 silver badges46 bronze badges

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

4 Comments

Sercan Noyan Germiyanoğlu Over a year ago

I'll try your code but there is a problem. The result shows all cities and then the result of searchBySubStringCharacter.

Vikas Over a year ago

The result all depends on your comparator logic.

Sercan Noyan Germiyanoğlu Over a year ago

there is a problem in for loop.

Sercan Noyan Germiyanoğlu Over a year ago

I've done my project and uploaded my github repository. There is a problem for seaching part. When I write "Moscow", it shows 2 results without showing 1 result. Can you check my project if you don't mind. github.com/Rapter1990/Binary-Search-Example

0xh3xa · Accepted Answer · 2020-04-30 22:55:44Z

0

You can add create city object from string and search like this:

  public static Integer[] searchBySubStringCharacter(List<City> list, String sub) {
        List<Integer> result = new ArrayList<>();

        Comparator<City> comparator = new Comparator<City>() {
            public int compare(City node1, City node2) {
                boolean node1Contains = node1.getCityName().contains(sub);
                boolean node2Contains = node2.getCityName().contains(sub);
                if (node1Contains && !node2Contains) {
                    return 1;
                } else if (!node1Contains && node2Contains) {
                    return -1;
                } else {
                    return 0;
                }
            }
        };

        Collections.sort(list, comparator);
        for (int i = 0; i < list.size(); i++) {
            int index = Collections.binarySearch(list, new City(sub), comparator);
            if (index >= 0)
                result.add(i);
        }

        return result.stream().toArray(Integer[]::new);
    }

, or avoid creating city object every iteration and accept city as an argument

public static Integer[] searchBySubStringCharacter(List<City> list, City sub) {
        List<Integer> result = new ArrayList<>();

        Comparator<City> comparator = new Comparator<City>() {
            public int compare(City node1, City node2) {
                boolean node1Contains = node1.getCityName().contains(sub.getCityName());
                boolean node2Contains = node2.getCityName().contains(sub.getCityName());
                if (node1Contains && !node2Contains) {
                    return 1;
                } else if (!node1Contains && node2Contains) {
                    return -1;
                } else {
                    return 0;
                }
            }
        };

        Collections.sort(list, comparator);
        for (int i = 0; i < list.size(); i++) {
            int index = Collections.binarySearch(list, sub, comparator);
            if (index >= 0)
                result.add(i);
        }

        return result.stream().toArray(Integer[]::new);
    }

answered Apr 30, 2020 at 22:55

0xh3xa

4,8672 gold badges17 silver badges30 bronze badges

13 Comments

Sercan Noyan Germiyanoğlu Over a year ago

the first one (public static Integer[] searchBySubStringCharacter(List<City> list, String sub)) get a full object list and the result of search like ("Sha").

Sercan Noyan Germiyanoğlu Over a year ago

there is a problem in for loop part.

Sercan Noyan Germiyanoğlu Over a year ago

I'm waiting for your response.

0xh3xa Over a year ago

By the way, why do you need to use BinarySearch in this situation

0xh3xa Over a year ago

Because the linear search will be good O(n) rather than the complexity of sort then apply search

|

Collectives™ on Stack Overflow

How can I implement binary search in Substring in function and two values in Comparator?

2 Answers 2

4 Comments

13 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

13 Comments

Your Answer

Sign up or log in

Post as a guest

Related