Sorting and Binary search using Java

Question

I was asked to sort and search an array. The sorting the array was simple and my code worked but then whenever I try to call the binary search method it works for the first element in the array but gives me "-1" as a result

My full code is as follows:

 public static void main(String[] args) {

    int[] array = new int[5];
    array[0] = 50;
    array[1] = 40;
    array[2] = 10;
    array[3] = 20;
    array[4] = 100;

sort(array, (array.length - 1));

      for (int x = 0; x < array.length; x++) {
        System.out.println(" " + array[x]);
    }
    System.out.println("");
    System.out.println("Binary search (R): " + rBsearch(array, 0, (array.length), 20));
}
    public static void sort(int[] a, int last) {
    if (last > 0) {
        int max = findMax(a, last);
        swap(a, last, max);
        sort(a, last - 1);
    }
}

public static int rBsearch(int[] L, int low, int high, int k) {


    int mid = (low + high) / 2;

    if (low > high) {
        return -1;
    } else if (L[mid] == k) {
        return mid;
    } else if (L[mid] < k) {
        return rBsearch(L, k, mid + 1, high);
    } else {
        return rBsearch(L, k, low, mid - 1);
    }
 }

public static int findMax(int[] arr, int last) {

    int max = 0;
    for (int i = 0; i <= last; i++) {
        if (arr[i] > arr[max]) {
            max = i;
        }
    }
    return max;
    }

public static void swap(int[] arr, int last, int max) {
    int temp = arr[last];
    arr[last] = arr[max];
    arr[max] = temp;
}

Have a look at your rBsearch method - look like you mix up bounds and key in the recursion calls. Maybe add a println to see whats actually happening. — Gyro Gearless
– Gyro Gearless, Commented Oct 21, 2013 at 10:53

Pratik Shelar · Accepted Answer · 2013-10-21 10:57:42Z

3

You goofed up the binary search intervals

public static int rBsearch(int[] L, int low, int high, int k) {


    int mid = (low + high) / 2;

    if (low > high) {
        return -1;
    } else if (L[mid] == k) {
        return L[mid];
    } else if (L[mid] < k) {
        return rBsearch(L, mid + 1, high, k);
    } else {
        return rBsearch(L, low, mid - 1, k);
    }
 }

answered Oct 21, 2013 at 10:57

Pratik Shelar

3,2227 gold badges33 silver badges51 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Scarl Over a year ago

I had a lot of things in mind while doing this! Anyways thanks!

shikjohari · Accepted Answer · 2013-10-21 10:57:00Z

2

You did a mistake in calling the rBsearch method in the following lines Instead of

else if (L[mid] < k) {
        return rBsearch(L, k, mid + 1, high); 
    } else {
        return rBsearch(L, k, low, mid - 1);
    }

You should use

else if (L[mid] < k) {
            return rBsearch(L,  mid + 1, high,k); //the order of the parameters
        } else {
            return rBsearch(L, low, mid - 1,k);
        }

answered Oct 21, 2013 at 10:57

shikjohari

2,28812 silver badges24 bronze badges

Comments

G.S · Accepted Answer · 2013-10-21 10:55:35Z

0

Easiest way is: Convert you array to list: Arrays.asList(array)

For sort: Collections#sort

For search: Collections#binarySearch

See this

answered Oct 21, 2013 at 10:55

G.S

11k8 gold badges43 silver badges56 bronze badges

Comments

Adeel Asghar · Accepted Answer · 2016-09-01 06:30:20Z

Take Array From User
Sort Array using Build-in Function of Java...

then Search Element using Binary Search....

    import java.lang.reflect.Array;
    import java.util.Arrays;
    import java.util.Scanner;

    class BinarySearch
    {
       public static void main(String args[])
       {
          int array[];

          Scanner input = new Scanner(System.in);
          System.out.println("Enter number of elements:");
         int Size_Of_Array = input.nextInt(); 


          array = new int[Size_Of_Array];

          System.out.println("Enter " + Size_Of_Array + " integers");

          for (int counter = 0; counter < Size_Of_Array; counter++)
              array[counter] = input.nextInt();

          Arrays.sort(array);
          System.out.println("Sorting Array is :-");
          for (int counter = 0; counter < Size_Of_Array; counter++)
              System.out.println(array[counter]);

          System.out.println("Enter the search value:");
          int  Searching_item = input.nextInt();

          int First_Index=0;
          int Last_Index=Size_Of_Array-1;
          int Middle_Index=(First_Index+Last_Index)/2;

          while(First_Index <= Last_Index)
          {
              if(array[Middle_Index] < Searching_item)
              {
                  First_Index=Middle_Index+1;
              }
              else if ( array[Middle_Index] == Searching_item ) 
              {
                System.out.println(Searching_item + " found at location " + (Middle_Index + 1) + ".");
                break;
              }
              else
              {
                  Last_Index = Middle_Index - 1;
              }
              Middle_Index = (First_Index + Last_Index)/2;

              if ( First_Index > Last_Index )
              {
                  System.out.println(Searching_item + " is not found.\n");
              }
          }
        }
    }

Result of BinarySearch

Collectives™ on Stack Overflow

Sorting and Binary search using Java

4 Answers 4

1 Comment

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

1 Comment

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related