Implementing Binary Search

Question

import java.io.*;
import java.lang.Integer;

class sort {
    public void find(int val, int a[], int n) {
        int mid = n / 2;
        System.out.println("the mid value is:" + a[mid]);
        if (a[mid] == val) {
            System.out.println("found " + a[mid] + " in position " + mid);
        } else if (a[mid] < val) {
            for (int i = mid; i < n; i++) {
                if (a[mid] == val) {
                    System.out.println("found" + val);
                }
            }
        } else if (a[mid] > val) {
            for (int i =0; i < mid; i++) {
                if (a[mid] == val) {
                    System.out.println("found" + val);
                }
            }
        }
    }


    public static void main(String args[])throws IOException {
        DataInputStream in = new DataInputStream(System.in);
        int temp;
        int a[] = new int[100];
        System.out.println("enter the nos of elements");
        int n = Integer.parseInt(in.readLine());
        for (int i =0; i < n; i++) {
            a[i] = Integer.parseInt(in.readLine());
        }
        for (int i =0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (a[i] > a[j]) {
                    temp = a[i];
                    a[i] = a[j];
                    a[j] = temp;
                }
            }
        }
        for (int i =0; i < n; i++) {
            System.out.println(a[i]);
        }

        System.out.println("enter the value to be searched");
        int val = Integer.parseInt(in.readLine());
        sort s = new sort();
        s.find(val, a, n);
    }
}

With the above code I want to find the user-defined value, from the existing array list using binary search. It checks only for middle value and not for the higher or lower value.

I think the loop doesn't works properly.

Kindly find a solution for this.

@True Soft, It's partially a binary search, but yes, it's not a binary search. I am not sure if @mano is ready for recursion yet. — strager
– strager, Commented Jul 18, 2010 at 5:46

strager · Accepted Answer · 2010-07-18 05:46:05Z

4

Your two inner loops:

for(int i=mid;i<n;i++) 
    {
     if (a[mid] ==val)
     System.out.println("found"+val); 
}



    for(int i=0;i<mid;i++)
{
 if (  a[mid] ==val)
     System.out.println("found"+val);
    }

Notice that you are accessing a[mid]. mid does not change throughout the loop; you meant to use a[i]. Try replacing mid with i.

Also, you may want to look into indenting your code. What editor are you using to write your code?

answered Jul 18, 2010 at 5:46

strager

90.3k27 gold badges139 silver badges181 bronze badges

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

Comments

rano · Accepted Answer · 2010-07-18 06:18:46Z

0

May I suggest to check the extreme positions values before calling again the search on the partition defined by those positions?

answered Jul 18, 2010 at 6:18

rano

5,6975 gold badges43 silver badges68 bronze badges

Comments

Gopi · Accepted Answer · 2010-07-18 08:40:32Z

0

Modify your find() function as below to recursively find the value under search which can be actually called as binary search -

  public void find(int val, int a[], int startIndex, int endIndex) {
    if(endIndex-startIndex == 1) {
       System.out.println("Not found");
       return;
    }
    int mid = startIndex + ((endIndex-startIndex) / 2);
    System.out.println("the mid value is:" + a[mid]);
    if (a[mid] == val) {
      System.out.println("found " + a[mid] + " in position " + mid);
    } else {
      if(a[mid] > val) {
        find(val, a, startIndex, mid);
      } else {
        find(val, a, mid, endIndex);
      }
    }
  }

You may call the function as with startIndex as zero and endIndex as length of array minus one.

edited Jul 18, 2010 at 8:40

answered Jul 18, 2010 at 5:56

Gopi

10.3k4 gold badges33 silver badges47 bronze badges

Collectives™ on Stack Overflow

Implementing Binary Search

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related