开发者

Implementing Binary Search

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) {
                    Sys开发者_运维百科tem.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.


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?


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


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.

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜