How can I search any Value in ArrayList via Binary Search

Question

I have a problem to get list including many index as a result of getting key value. I have an error in my code.

My City class shown below.

public class City implements Serializable{
    private String cityName;
    private String countryName;
    ...
}

My Arraylist contains city names and its country Names as shown below.

Shanghai, China
...
...

As Arraylist is very large size like 50000, I apply binary Search to search any character or word in the list.

I want to search any character or Word which is sensitive to Uppercase or lowercase and retrieve back their indexs.

How can I do this process?

The code run according to the defined characher, character string or word shown below.

Sample Examples

Enter the word of character which I want to search : W
Enter the word of character which I want to search : Sha
Enter the word of character which I want to search : Shanghai

Here is my code snippet shown below.

Scanner scanner = new Scanner(System.in);
System.out.print("Enter the word of character which I want to search : ");
String charWord = scanner.nextLine();
System.out.println("Search " + charWord);
Integer[] index = BinarySearch.binarySearch(cities, charWord);
System.out.println(index.toString());


public static Integer[] binarySearch( ArrayList<City> list, String key ) {
        Comparable comp = (Comparable)key;
        List<Integer> arrlist = new ArrayList<Integer>();
        Integer arr[] = null;
        int res = -1, min = 0, max = list.size() - 1, pos;
        while( ( min <= max ) && ( res == -1 ) ) {
            pos = (min + max) / 2;
            int comparison = comp.compareTo(key.contains(list.get(pos).getCityName()));
            if( comparison == 0) {
                res = pos;
                arrlist.add(res);
            }
            else if( comparison < 0)
                max = pos - 1;
            else
                min = pos + 1;
        }

        return arrlist.toArray(arr);
    }

what does this line : comp.compareTo(key.contains(list.get(pos).getCityName())); mean? are you looking for an exact match or some percentage of match like Shanghai and Shangall for e.g.? If the latter is the case you need to do a nearest match and you need to write a separate function to compare two strings and give you a measure of equality. contains only tells you if a string is present in another string. Also I believe a data structure like Ternary Search Trie would also be more efficient in that case. — SomeDude
– SomeDude, Commented Apr 24, 2020 at 14:14
@SomeDude I shared sample input. That's why I use contains method but it doesn't work. — Sercan Noyan Germiyanoğlu
– Sercan Noyan Germiyanoğlu, Commented Apr 24, 2020 at 14:17
Enter the word of character which I want to search : W : Does this mean that you want to get all Strings which start with W ? or contains W ? or ends with W? In any case it seems you are looking for something like prefix match in a set of strings for which a trie is more suited I believe. — SomeDude
– SomeDude, Commented Apr 24, 2020 at 14:20
@SomeDude contains W. Every city names starts with Upper letter. Therefore It gets city names starting with W. But I can use w(lower case) . It get city names containing w letter. — Sercan Noyan Germiyanoğlu
– Sercan Noyan Germiyanoğlu, Commented Apr 24, 2020 at 14:22

0xh3xa · Accepted Answer · 2020-04-24 14:48:37Z

1

This will search using city name

    private static class City {

        private String country;
        private String cityName;

        public City(String cityName, String country) {
            this.cityName = cityName;
            this.country = country;
        }

        public void setCityName(String cityName) {
            this.cityName = cityName;
        }

        public String getCityName() {
            return cityName;
        }

        public String getCountry() {
            return country;
        }

        public void setCountry(String country) {
            this.country = country;
        }

        @Override
        public String toString() {
            return cityName;
        }
    }

    public static void main(String[] args) {
        List<City> list = new ArrayList<>();
        list.add(new City("Shanghai", "Shanghai"));
        list.add(new City("USA", "USA"));
        list.add(new City("China", "China"));
        list.add(new City("Germany", "Germany"));
        list.add(new City("China", "China"));
        list.add(new City("china", "china"));
        Integer[] indices = binarySearch(list, "China");
        for (int i = 0; i < indices.length; i++) {
            System.out.print(indices[i] + " ");
        }
        System.out.println();
    }

    public static Integer[] binarySearch(List<City> cities, Comparable key) {
        List<Integer> arrList = new ArrayList<Integer>();
        int lo = 0, hi = cities.size() - 1, mid;
        cities.sort((str1, str2) -> str1.getCityName().compareTo(str2.getCityName()));
        System.out.println(cities);
        while (lo <= hi) {
            mid = lo + (hi - lo) / 2;
            int cmp = key.compareTo(cities.get(mid).getCityName());
            if (cmp == 0) {
                arrList.add(mid);
                lo = mid + 1;
            } else if (cmp < 0)
                hi = mid - 1;
            else
                lo = mid + 1;
        }
        return arrList.stream().toArray(Integer[]::new);
    }

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

, output

[China, China, Germany, Shanghai, USA, china]
0 1

edited Apr 24, 2020 at 14:48

answered Apr 24, 2020 at 14:06

0xh3xa

4,8672 gold badges17 silver badges30 bronze badges

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

22 Comments

Sercan Noyan Germiyanoğlu Over a year ago

I edit my post. It works for not only words but also character or charater string.

0xh3xa Over a year ago

Yes, any wrapper classes have Comparable, so Character, Integer, etc

0xh3xa Over a year ago

@TonyBrand do you want to search over the characters in the city name also?

Sercan Noyan Germiyanoğlu Over a year ago

Exactly, This code works for both cases. But it doesn't work.

Sercan Noyan Germiyanoğlu Over a year ago

Your City class justly only one value. My city class has two values cityName and country. I edited my post again.

|

Collectives™ on Stack Overflow

How can I search any Value in ArrayList via Binary Search

1 Answer 1

22 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

22 Comments

Your Answer

Sign up or log in

Post as a guest

Related