Welcome to the Linux Foundation Forum!

Binary search

This technique uses a binary search to find a target integer in a RandomAccessFile. It is just concerned with integers.
This is the code:

//determines if a target number is in a RandomAccessFile using a binary search
//tracks the number of times it took to find that the number was/wasn't in the file
public static void binarySearch(){
Scanner input = new Scanner(System.in);
int target = 0; //the number being searched for
boolean targetFound = false; //indicates if the target is found
int searchCount = 0; //the number of times it took to find that the number was/wasn't in the file

System.out.print("Please enter the number you wish to search for: ");

target = input.nextInt();

try{
    RandomAccessFile raf = new RandomAccessFile("Project10.dat", "r");
    long low = 0;
    long high = raf.length() - 1;
    int cur = 0;

    while(high >= low){         
        long mid = (low + high) / 2;
        raf.seek(mid);
        cur = raf.readInt();
        System.out.println(cur); //for debugging

        searchCount++;

        if(target < cur){
            high = mid - 4;
        }
        else if(target == cur){
            targetFound = true;
            break;
        }
        else{
            low = mid + 4;
        }
    }

    raf.close();
}
catch(FileNotFoundException e){
    e.printStackTrace();
}
catch (IOException e){
    e.printStackTrace();
}

if(targetFound == true){
    System.out.println("The number " + target + " is in the file. It took " + searchCount + " tries to discover this.");
}
else{
    System.out.println("The number " + target + " is not in the file. It took " + searchCount + " tries to discover this.");
}

}//end method binarySearch

I've tried everything, but I'm getting the wrong results. Because a raf comprises bytes and an integer contains four bytes, I figured I'd just decrease the high by four and increase the low by four, as described in this blog, where the identical operations were performed by one in a typical binary search. Apparently, this is not the case, and I'm still struggling to understand binary I/O in general. Help?

Answers

  • fcioanca
    fcioanca Posts: 1,866

    Hi @vikash11

    Can you please advise if your post is related to a training course, or to a different Linux topic? This forum is dedicated to a specific initiative, and if you post in the incorrect forum, your post will be overlooked.

    Regards,
    Flavia

Categories

Upcoming Training