尽管元素存在，二进制搜索仍返回 -1

Question

对于这个程序，我尝试使用二进制搜索来查找给定数组的特定元素，例如标题、年份或艺术家。现在，我只测试标题和年份，因为它们都是字符串。但似乎对于我输入的某些输入，程序会 return -1，即使我输入的输入存在于数组中。我不确定为什么会这样。

首先是测试器class，第二个代码是构造器class。

public class TestMusic
{
    public static void printMusic(Music[] arr)
    {
        for (Music music : arr)
        {
            System.out.println(music.toString());
        }
    }
    
    public static int binaryTitle(Music[] arr, String title)
    {
        int l = 0, r = arr.length - 1;
        while (l <= r) {
            int m = l + (r - l) / 2;

            int res = title.compareTo(arr[m].getTitle());

            // Check if x is present at mid
            if (res == 0)
                return m;

            // If x greater, ignore left half
            if (res > 0)
                l = m + 1;

                // If x is smaller, ignore right half
            else
                r = m - 1;
        }

        return -1;
    }
       

    
    public static int binaryArtist(Music[] arr, String artist)
    {
        int l = 0, r = arr.length - 1;
        while (r - l >= 1) {
            int m = l + (r-l) / 2;

            int res = artist.compareTo(arr[m].getArtist());

            
            if (res == 0)
            {
                return m;
            }

            if (res > 0)
            {
                l = m + 1;
            }

            else
            {
                r = m - 1;
            }
        }

        return -1;
    }
    
    public static void main(String[]args)
    {
        Music[] arr = new Music[12];
        arr[0] =  new Music("Montero", 2021, "Lil Nas X");
        arr[1] =  new Music("Dynamite", 2020, "BTS");
        arr[2] =  new Music("Bad Guy", 2019, "Billie Eilish");
        arr[3] =  new Music("Sicko Mode", 2018, "Travis Scott");
        arr[4] =  new Music("Shape of You", 2017, "Ed Sheeran");
        arr[5] =  new Music("Heathens", 2016, "Twenty One Pilots");
        arr[6] =  new Music("See You Again", 2015, "Wiz Khalifa");
        arr[7] =  new Music("All About That Bass", 2014, "Meghan Trainor");
        arr[8] =  new Music("Wrecking Ball", 2013, "Miley Cyrus");
        arr[9] =  new Music("Paradise", 2011, "Coldplay");
        arr[10] = new Music("Shake it Off", 2014, "Taylor Swift");
        arr[11] = new Music("Savage", 2021, "Aespa");
        
        System.out.println("Original:");
        printMusic(arr);
        
        
        
        System.out.println("\nBinary searching Sicko Mode: Index " + binaryTitle(arr, "Sicko Mode"));
        System.out.println("\nBinary searching Taylor Swift: Index " + binaryArtist(arr, "Taylor Swift"));
        
        
        
        
        
    }
}

public class Music
{
    // instance variables
    private int year;
    private String title;
    private String artist;

    // Constructor for objects of class Music
    public Music(String t, int y, String a)
    {
        // initialize instance variables
        title = t;
        year = y;
        artist = a;
    }

    public String getTitle()
    {
        return title;
    }
   
    public void setTitle(String t)
    {
        title = t;
    }
   
    public String getArtist()
    {
        return artist;
    }
    
    public void setArtist(String a)
    {
        artist = a;
    }
   
    public int getYear()
    {
        return year;
    }
    
    public void setTitle(int y)
    {
        year = y;
    }
   
    public String toString()
    {
        String str = String.format( "%-25s %4d   %-20s ", title,  year , artist);
        return str;
    }
}

Answer 1

要使二分搜索正常工作，必须以某种方式对其进行排序。如果您按年份搜索它，则需要将其从小到大排序。如果您按标题搜索，则这些标题必须按字母顺序排列，与艺术家相同。例如：

{1,4,3,2,5} //searching for 4 returns -1 because it's looking between 3 and 5 and only finding 2.
{1,2,3,4,5} //searching for 4 returns 3 because it looks between 3 and 5 and finds 4 at index 3.

Answer 2

二分查找需要排序数组。如果您使用未排序的数组，二分查找很可能找不到您需要的内容。对于这种类型的东西，您需要顺序搜索。

示例：

[0, 3, 7, 8, 12, 56, 2]
//say you have this array, and you're looking for number 2,
//your function will compare 2 to the middle element: 8. 
//2 < 8, so it will throw out everything above 8. 
[0, 3, 7]
//Obviously 2 is not there. But it was there originally.
//The problem is it was unsorted

Answer 3

我可以确认你只能对一种类型的二分查找其对应的排序。所以标题二分搜索只能在标题排序后发生。

尽管元素存在，二进制搜索仍返回 -1

Binary Search returning -1 in spite of the element existing

java

arraylist