Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.Scanner;
- public class BinaryIntSearch
- {
- public static void main(String[] args)
- {
- search();
- }
- public static void search()
- {
- //not confident my code works 100%, so not using ArrayUtil yet)
- //int[] randomArray = ArrayUtil.randomIntArray(20, 100);
- //This is a sorted array; I'm not testing mergesort yet
- int[] randomArray = {1 , 4, 5, 8, 9, 10, 11, 15};
- Scanner searchInput = new Scanner(System.in);
- int searchInt = searchInput.nextInt();
- System.out.println( findNumber(randomArray, 9) );
- }
- private static int findNumber(int[] searchedArray, int searchTerm)
- {
- //Merge sorts the array
- //I should really move the merge sorting into the search() method
- MergeSorter mergesorted = new MergeSorter(searchedArray);
- mergesorted.sort();
- //It's complicated as to why I created this extra array; ask me over msn
- int[] newSearchedArray = new int[searchedArray.length];
- System.arraycopy(mergesorted, 0, newSearchedArray, 0, newSearchedArray.length);
- //splits the array into firstHalf and secondHalf
- int[] firstHalf = new int[searchedArray.length / 2];
- int[] secondHalf = new int[searchedArray.length - firstHalf.length];
- System.arraycopy(newSearchedArray, 0, firstHalf, 0, firstHalf.length);
- System.arraycopy(newSearchedArray, firstHalf.length, secondHalf, 0, secondHalf.length);
- //declare a boolean variable to store whether the search term is in firstHalf or secondHalf
- boolean isIt1;
- //Not quite sure if my while loop condition is an effective one (stops when its supposed to)
- while (firstHalf.length > 1)
- {
- //for convenience sake so I don't have to type in all that crap every time
- int firstRep = firstHalf.length - 1;
- int secondRep = secondHalf.length - 1;
- //Quickly checks if the firstHalf or secondHalf representative is equivalent to the search term.
- //If it is, why not just break the loop there and then
- //Checks if firstRep is bigger than the search term (if it is, we know search term is not in firstHalf)
- //If secondRep is bigger than search term, the search term ain't going to be anywhere.
- if (firstHalf[firstRep] == searchTerm) return firstRep; else
- if (secondHalf[secondRep] == searchTerm) return secondRep; else
- if (firstHalf[firstRep] > searchTerm) isIt1 = false; else
- if (secondHalf[secondRep] > searchTerm) return -1;
- //Is the search term in the firstHalf? Then work with the firstHalf
- //Otherwise work with the secondHalf...
- if (isIt1 = true)
- {
- //if search term is in firstHalf, split firstHalf into iFirstHalf and iSecondHalf
- int[] iFirstHalf = new int[firstHalf.length / 2];
- int[] iSecondHalf = new int[firstHalf.length - iFirstHalf.length];
- System.arraycopy(firstHalf, 0, iFirstHalf, 0, iFirstHalf.length);
- System.arraycopy(firstHalf, iFirstHalf.length, iSecondHalf, 0, iSecondHalf.length);
- //copy iFirstHalf and iSecondHalf to firstHalf and secondHalf (respectively)
- //This is to make sure that we can work with firstHalf and secondHalf again (it won't be the old halves)
- firstHalf = new int[iFirstHalf.length];
- secondHalf = new int[iSecondHalf.length];
- System.arraycopy(iFirstHalf, 0, firstHalf, 0, firstHalf.length);
- System.arraycopy(iSecondHalf, 0, secondHalf, 0, secondHalf.length);
- }else
- {
- //same thing, except with secondHalf
- int[] iFirstHalf = new int[secondHalf.length / 2];
- int[] iSecondHalf = new int[secondHalf.length - iFirstHalf.length];
- System.arraycopy(secondHalf, 0, iFirstHalf, 0, iFirstHalf.length);
- System.arraycopy(secondHalf, iFirstHalf.length, iSecondHalf, 0, iSecondHalf.length);
- firstHalf = new int[iFirstHalf.length];
- secondHalf = new int[iSecondHalf.length];
- System.arraycopy(iFirstHalf, 0, firstHalf, 0, firstHalf.length);
- System.arraycopy(iSecondHalf, 0, secondHalf, 0, secondHalf.length);
- }
- }
- //well, if nothing works, return a -1 to indicate that this is screwed
- return -1;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement