Binary Search: Searching last & first Element

User_AYF65

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.

User_AYF65

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.

TPD-Opitz

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

bye

TPD

User_AYF65

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

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

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

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

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.