Implementing Binary Search

Answer 1

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?

Answer 2

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.

Answer 3

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

Answer 4

import java.util.Arrays;
import java.util.Scanner;

class sort {
    public static void main(String args[]) {
        //DataInputStream in = new DataInputStream(System.in);
        // Use scanner instead of datainputstream for easier int parsing
        Scanner sc = new Scanner(System.in);
        //int temp;
        // no need for this var
        //int a[] = new int[100];
        // declare array of correct size when we knoew it
        System.out.println("enter the nos of elements");
        //int n = Integer.parseInt(in.readLine());
        int n = sc.nextInt();
        int a[] = new int[n];

        for (int i = 0; i < n; i++) {
            //a[i] = Integer.parseInt(in.readLine());
            a[i] = sc.nextInt();
        }
        /*
        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;
                }
            }
        }
        */
        Arrays.sort(a);

        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());
        int val = sc.nextInt();
        //sort s = new sort();
        //s.find(val, a, n);
        int index = Arrays.binarySearch(a, val);
        if (index >= 0)
            System.out.println("found "+a[index]+" in position "+ index);
        else
            System.out.println("value " + val + " does not exist");
    }
}