CODEWITHSUNDEEP
java
Jessica Brister
Jessica Brister

Reputation: 1

how to do a binary search without using an array in java

I'm trying to create a binary search that doesn't use an array. It also needs to count how many searches it does until it finds the number. I also have to use a randomaccessfile.

RandomAccessFile raf=new RandomAccessFile(new File("Project 10"),"rw");

//writing in random numbers. Different numbers will be used when it is being tested

raf.writeInt(-5);
raf.writeInt(-1);
raf.writeInt(122);
raf.writeInt(124);
raf.writeInt(125);
raf.writeInt(256);

user input what number do you want to search for. I need to do this without using the scanner class. the method to do this will be very helpful

I know this is how you do a binary search with an array. I need help figuring out how to do it without an array

public static int binarySearch(int[] list, int key) {
    int low = 0;
    int high = list.length - 1;

    while (high >= low) {
        int mid = (low + high) / 2;
        if (key < list[mid])
            high = mid - 1;
        else if (key == list[mid])
            return mid;
        else
            low = mid + 1;
    }
    return -low - 1; // Now high<low, key not found
}

Upvotes: 0

Views: 2263

Answers (3)

Jessica Brister
Jessica Brister

Reputation: 1

Would something like this work?

public static int binarySearch(int raf//for the file?, int key//for input?){
int low=0;
int high=raf.length()-1
while (high>=low){
int mid=(low+high)/2;
if (key<raf.[mid])// Does the [] automatically make it an array
high=mid-1;
else if (key==raf.[mid])
return mid;
else
low=mid+1;
}
return-low-1//now high < low, key not found
}
}

Upvotes: 0

CodeChimp
CodeChimp

Reputation: 8154

You don't need an array or a List if you treat your file as the array. Assuming the file is sorted, the pseudo code would go something like

  1. Get the number of lines in the file (may need to guess...not sure how you could count new lines)
  2. Read the value at 1/2 the total number of lines
  3. If the value is same, done. If smaller, repeat using the first half of the file. If larger, repeat with the second half of the file.

Upvotes: 1

Christian Bongiorno
Christian Bongiorno

Reputation: 5648

This isn't really a java specific question as much as it is an algorithms questions. Though not stated, your binarySearch is obviously predicated on the file somehow magically getting sorted.

That said, you know that the raf.writeInt(xxx) is going to write a normalized byte-length value to the file. Treat the file itself as an array where each index position is a[i * 4] == so, create little functions that compute 'mid' 'low' and 'high' as multiples of the desired index.

Google for "external sorting"

Upvotes: 1

Related Questions