Forum Stats

  • 3,726,738 Users
  • 2,245,248 Discussions
  • 7,852,382 Comments

Discussions

Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Binary Search: Searching last & first Element

User_AYF65
User_AYF65 Member Posts: 135 Red Ribbon
edited April 2016 in New To Java

Hi,

I have coded Binary Search in java but its returning -1 when i am trying to search last or first element. If first works then last doesnt work & if last works first doesnt work. My code is given below:

import javax.swing.*;

public class BinarySearch{

   int[ ] Array = new int[10];

   BinarySearch(int[ ] a ) {

      Array = a;

   }

   int BinarySearchAlg(int num, int first, int last ) {

      int index=-1;

     

      if(first < last) {

          int mid = first + ((last - first) / 2);

          //int mid = (first + last)/2;

  JOptionPane.showMessageDialog(null, "mid= " + mid);

          if(num == Array[mid])

             index = mid;

          else if(num < Array[mid])

             index = BinarySearchAlg(num, first, mid-1);

          else

        index = BinarySearchAlg(num, mid+1, last);

       }

       return index;

   }

   public static void main(String[ ] args) {

  

      int[ ] a = {1, 12, 19, 56, 100, 134, 145, 178, 199, 201};

      BinarySearch obj = new BinarySearch(a);

      int index=obj.BinarySearchAlg(1, 1, 10);

      //int index=obj.BinarySearchAlg(201, 0, 9);

      JOptionPane.showMessageDialog(null, "index= " + index);

 

   }

}

When i tried the following statement:

int index=obj.BinarySearchAlg(1, 1, 10);

it returns -1 (i.e it cant search 1 in the array

& when i tried:

int index=obj.BinarySearchAlg(201, 0, 9);

it returns -1(i.e. it cant search 201 in the array.


Somebody please guide me.


Zulfi.

Best Answer

  • User_AYF65
    User_AYF65 Member Posts: 135 Red Ribbon
    edited April 2016 Accepted Answer

    Hi,

    Thanks everybody. I am able to correct my program:

    import javax.swing.*;

    public class BinarySearch{

       int[ ] Array = new int[10];

       BinarySearch(int[ ] a ) {

          Array = a;

       }

       int BinarySearchAlg(int num, int first, int last ) {

          int index=-1;

        

         if(first <= last) {

              //int mid = first + ((last - first) / 2);

              int mid = (first + last)/2;

      JOptionPane.showMessageDialog(null, "mid= " + mid + "first ="+ first + "last=" + last);

              if(num == Array[mid])

                 index = mid;

              else if(num < Array[mid])

                 index = BinarySearchAlg(num, first, mid-1);

              else{

                 

            index = BinarySearchAlg(num, mid+1, last);

               

             }

           }

           return index;

       }

       public static void main(String[ ] args) {

     

          int[ ] a = {1, 12, 19, 56, 100, 134, 145, 178, 199, 201};

          BinarySearch obj = new BinarySearch(a);

          int index=obj.BinarySearchAlg(199, 0, 10);

          //int index=obj.BinarySearchAlg(201, 0, 9);

          JOptionPane.showMessageDialog(null, "index= " + index);

       }

    }

    Correction is highlighted.

    Zulfi.

Answers

  • TPD-Opitz
    TPD-Opitz Member Posts: 2,465 Silver Trophy
    edited April 2016

    what does "it does not work" mean in particular?

    bye

    TPD

  • User_AYF65
    User_AYF65 Member Posts: 135 Red Ribbon
    edited April 2016

    Hi,

    <

    what does "it does not work" mean in particular?>

    It means that its not able to search the first & last element.

    Zulfi.

  • Jiri.Machotka-Oracle
    Jiri.Machotka-Oracle Member Posts: 5,078
    edited April 2016

    If first = last then -1 is returned without checking the value.

    Why don't you trace your program? You'd see it yourself.

  • User_AYF65
    User_AYF65 Member Posts: 135 Red Ribbon
    edited April 2016 Accepted Answer

    Hi,

    Thanks everybody. I am able to correct my program:

    import javax.swing.*;

    public class BinarySearch{

       int[ ] Array = new int[10];

       BinarySearch(int[ ] a ) {

          Array = a;

       }

       int BinarySearchAlg(int num, int first, int last ) {

          int index=-1;

        

         if(first <= last) {

              //int mid = first + ((last - first) / 2);

              int mid = (first + last)/2;

      JOptionPane.showMessageDialog(null, "mid= " + mid + "first ="+ first + "last=" + last);

              if(num == Array[mid])

                 index = mid;

              else if(num < Array[mid])

                 index = BinarySearchAlg(num, first, mid-1);

              else{

                 

            index = BinarySearchAlg(num, mid+1, last);

               

             }

           }

           return index;

       }

       public static void main(String[ ] args) {

     

          int[ ] a = {1, 12, 19, 56, 100, 134, 145, 178, 199, 201};

          BinarySearch obj = new BinarySearch(a);

          int index=obj.BinarySearchAlg(199, 0, 10);

          //int index=obj.BinarySearchAlg(201, 0, 9);

          JOptionPane.showMessageDialog(null, "index= " + index);

       }

    }

    Correction is highlighted.

    Zulfi.

  • Jiri.Machotka-Oracle
    Jiri.Machotka-Oracle Member Posts: 5,078
    edited April 2016

    The fact that a program produces correct results does not mean it is a correct answer - binary search is not an algorithm that needs to be recursive (and as such it should not be):

       int BinarySearchAlg(int num, int first, int last ) {

          

            while (true) {

              

                if (first > last) {

                    return -1;

                }

              

                if (first == last)

                    if (Array[first] == num) {

                        return first;

                    } else {

                        return -1;

                    }

              

                int mid = first + ((last - first) / 2);

              

                if(num == Array[mid]) {

                    return mid;

                }

              

                if (num < Array[mid]) {

                    last = mid -1;

                } else {

                    first = mid + 1;

                }

              

            }

          

       }

  • User_AYF65
    User_AYF65 Member Posts: 135 Red Ribbon
    edited April 2016

    Hi,

    Thanks for referring Iterative version of Binary Search. Sorry your if construct is confusing. I got the following:

    public class BinarySearchIterative{

       int[ ] Array = new int[10];

    BinarySearchIterative(int[ ] a ) {

          Array = a;

       }

       int BinarySearchAlg(int num, int first, int last ) {

          int index=-1;

         

          while(first <= last) {

             int mid= (first + last)/2;

             if(num < Array[mid])

                last = mid -1;

             else if(num > Array[mid])

                first = mid + 1;

             else

                return mid;

          }

               

           return index;

       }

       public static void main(String[ ] args) {

     

          int[ ] a = {1, 12, 19, 56, 100, 134, 145, 178, 199, 201};

    BinarySearchIterative obj = new BinarySearchIterative(a);

          int index=obj.BinarySearchAlg(201, 0, 10);

          //int index=obj.BinarySearchAlg(201, 0, 9);

    JOptionPane.showMessageDialog(null, "index= " + index);

       }

    }

    Any way i appreciate your quick response. Indeed you are a great helper.

    Zulfi.

    User_AYF65
This discussion has been closed.