时间戳

首页 > 解决方案 > 二分查找只返回一条语句

java - 二分查找只返回一条语句

问题描述

我是二进制搜索的新手，我尝试了一个程序来查找用户输入的值的位置。然而，我的代码似乎只返回一个低=-1 值，这导致程序说“找不到该值”。我认为我的二进制搜索代码做错了，但我对这些没有经验并且可能遗漏了什么？这是我的二进制搜索代码：

static public int search (int[]numbers,int target, int count)
{
    int high = numbers.length;
    int low = -1;
    int middle = (high+low)/2;
    
    while(high-low>1)
    {
        count++;
        middle = (high+low)/2;
        if(numbers[middle]>target)
        {
            high = middle;
        }
        else if(numbers[middle]<target)
        {
            low = middle;
        }
        else if(numbers[middle] == target)
        {
            break;
        }
        System.out.println(numbers[middle]);
        System.out.println(middle);
    }
        if(low == -1 || numbers[low]!=target)
        {
            low=-1;
            return low;
            
        }
        else
        {
            return low;
        }
        
        
}

这是要求用户输入的代码的一部分：

public static void main(String[] args) throws IOException {
    DataInputStream input = new DataInputStream(System.in);
    int [] numbers = new int [50000];
    int target;
    int count=0;
    
    try
    {
        BufferedReader br = new BufferedReader(new FileReader("randNums.txt")); 
        for(int i=0;i<50000;i++)
        {
            numbers[i]=Integer.parseInt(br.readLine());
        }
        br.close();
        
        Arrays.sort(numbers);
        
        System.out.print("Choose a number between 1-100000000 to search for: ");
        target = Integer.parseInt(input.readLine());
        
        
        int low = search(numbers, target, count);
        if(low==-1)
        {
            System.out.println("The number was not on the list.");
        }
        else
        {
            System.out.println("The number is at position " + low);
            System.out.println("It took " + count + " comparisons to find the number.");
        }
        
    }

标签： javabinary-search

解决方案

您的搜索功能存在一些问题。在 search 函数中二分查找的实现应该是这样的：

    static public int search (int[]numbers,int target, int count)
    {
        int high = numbers.length-1;
        int low = 0;
        int middle = (high+low)/2;
        
        while(high>=low)
        {
            count++;
            middle = (high+low)/2;
            if(numbers[middle]==target)
            {
                return middle;
            }
            else if(numbers[middle]<target)
            {
                low = middle+1;
            }
            else if(numbers[middle]>target)
            {
                high=middle-1;
            }
            System.out.println(numbers[middle]);
            System.out.println(middle);
        }
         return -1;
                    
    }

推荐阅读