Results 1 to 11 of 11

Thread: binary search

  1. #1
    tranceluv is offline Member
    Join Date
    Jan 2008
    Posts
    5
    Rep Power
    0

    Default binary search

    hey i got confused with this and maybe someone can help me...

    i was experimenting about sorting a randomly generated array of 100 integers with binary search.. however i have some trouble..

    heres d code:

    class iamangry
    {

    public int binarySearch(int arr[], int key, int n)
    {
    int low = 0;
    int ri = (arr[n]+ 1);
    int mid;

    do{ mid = ((low + ri)/2);
    if(key < arr[mid]){
    ri = (mid - 1);
    }
    else low = mid + 1;
    }
    while (key == arr[mid]);
    if(low < ri){
    return -1;
    }
    else return mid;
    }



    public static void main(String[] args){
    int x = 100;
    int[]arr = binarySearch[x];
    for(int n = 0; n < a.length; n++){
    arr[n] = 1 + (int)(Math.random() *100);
    }
    for(int t=1; t<=100; t++){
    System.out.print(""+arr[t]+" ");
    }
    }
    }



    the problem seems to be actually in: int[]arr = binarySearch[x]; ...

    any help please? thanks

  2. #2
    CaptainMorgan's Avatar
    CaptainMorgan is offline Moderator
    Join Date
    Dec 2007
    Location
    NewEngland, US
    Posts
    835
    Rep Power
    8

    Default

    One thing you need to understand about Binary Search, is that it is a search function for some value or object, thus your array is assumed to be already sorted. You're looking for some value within in the array and trying to discover its location.

    I altered your code to form the below, although not thoroughly tested.. I hope you get the idea.
    Java Code:
    public class BinarySearch {
      public int binarySearch(int arr[], int key, int size) {
        int low = 0;
        int mid = 0;    
        int high = size;
    
        while (low <= high) {
          mid = ((low + high) / 2);
        
          if (key < arr[mid]) {
            high = (mid - 1);
          } else { 
            low = mid + 1; 
          }       
        } 
        
        if (low < high) { 
          return -1;
        } else { 
          return mid;
        }       
      }
    
      public static void main(String[] args){
        int SIZE = 20;
        int[] arr = new int[SIZE];
        int key = 5;
        
        for (int i = 0, k = 0; i < SIZE; i++, k++) {
          arr[k] = i; //(1 + (int)(Math.random() * 100));
        }
        
        BinarySearch bs = new BinarySearch();    
        
        for (int j = 0; j <= arr.length - 1; j++) {
          System.out.println(arr[j]);
        }
        
        System.out.println("Array size: " + arr.length);
        System.out.println("Value found at index " + bs.binarySearch(arr, key, SIZE));
      }  
    }
    Vote for the new slogan to our beloved Java Forums! (closes on September 4, 2008)
    Want to voice your opinion on your IDE/Editor of choice? Vote now!
    Got a little Capt'n in you? (drink responsibly)

  3. #3
    tranceluv is offline Member
    Join Date
    Jan 2008
    Posts
    5
    Rep Power
    0

    Default

    ah ok ic..

    so how can i sort an array of randomly generated numbers?

    cheers

  4. #4
    CaptainMorgan's Avatar
    CaptainMorgan is offline Moderator
    Join Date
    Dec 2007
    Location
    NewEngland, US
    Posts
    835
    Rep Power
    8

    Default

    Quote Originally Posted by tranceluv View Post
    ah ok ic..

    so how can i sort an array of randomly generated numbers?

    cheers
    Check the API for an ArrayList, fill it with your random values... upon which I believe you have to use Collections.sort() to sort. Someone will correct me if I'm wrong.

    Best of luck!
    Vote for the new slogan to our beloved Java Forums! (closes on September 4, 2008)
    Want to voice your opinion on your IDE/Editor of choice? Vote now!
    Got a little Capt'n in you? (drink responsibly)

  5. #5
    afsina is offline Member
    Join Date
    Jan 2008
    Posts
    24
    Rep Power
    0

    Default

    i am assuming you are doing binary search code because you want to practice. Because obviously Arrays.binarySearch(...) does the thing.

  6. #6
    tranceluv is offline Member
    Join Date
    Jan 2008
    Posts
    5
    Rep Power
    0

    Default

    Quote Originally Posted by afsina View Post
    i am assuming you are doing binary search code because you want to practice. Because obviously Arrays.binarySearch(...) does the thing.
    can you help me out using Arrays.binarySearch(...) pls? tks

  7. #7
    afsina is offline Member
    Join Date
    Jan 2008
    Posts
    24
    Rep Power
    0

    Default

    well, did you read the java doc?
    there is also a handy "sort" method there. first show me what do you have, then we can analyze the problem.

  8. #8
    afsina is offline Member
    Join Date
    Jan 2008
    Posts
    24
    Rep Power
    0

    Default

    By the way, leanring the internals of binary search algorithm is a very important thing, i strongly suggest understanding the way it works first (this is one of the favorite questions asked in job interviews even maybe by Google). But if you are developing an application that requires binary search, by all means use the built in Facilities in Java, like Arrays, Collections etc.

  9. #9
    tranceluv is offline Member
    Join Date
    Jan 2008
    Posts
    5
    Rep Power
    0

    Default

    Quote Originally Posted by afsina View Post
    well, did you read the java doc?
    there is also a handy "sort" method there. first show me what do you have, then we can analyze the problem.
    well i thought that this method could sort the random-number array :(

    public int binarySearch(int arr[], int key, int size) {
    int low = 0;
    int mid = 0;
    int high = size;

    while (low <= high) {
    mid = ((low + high) / 2);

    if (key < arr[mid]) {
    high = (mid - 1);
    } else {
    low = mid + 1;
    }
    }

    if (low < high) {
    return -1;
    } else {
    return mid;
    }
    }

    actually i'm just starting to learn what sorting is and binary search seems one of the most efficient

  10. #10
    afsina is offline Member
    Join Date
    Jan 2008
    Posts
    24
    Rep Power
    0

    Default

    No, binary search is used for finding an element in an already sorted array quickly. For example if you have a sorted integer array like this:
    a[]={1,2,4,5,6,7,9,10,11,12,14,16,19,21,22}
    binary search can find the position of "19" in only three steps. However, as you see the array is already sorted.

    there are several sorting algorithms, if you want to learn ebout them, you can start with easy ones, such as selection sort, bubble sort or insertion sort. there are more complicated sort algorithms also such as quick sort, merge sort, radix sort or heap sort.

    Java platform uses a modified merge sort, and qick sort for its sort facilities. There are Arrays.sort() for arrays, and Collections.sort() for Lists available. But i got that you are in the learning phase, not sur eif you want to use them.

    Make a search in wikipedia about search algorithms or binary search, you can see several different implementations in various languages in the links area. Or Google it. For binary search or sort, you can also check how java is doing it by checking the source.

  11. #11
    tranceluv is offline Member
    Join Date
    Jan 2008
    Posts
    5
    Rep Power
    0

    Default

    Quote Originally Posted by afsina View Post
    No, binary search is used for finding an element in an already sorted array quickly. For example if you have a sorted integer array like this:
    a[]={1,2,4,5,6,7,9,10,11,12,14,16,19,21,22}
    binary search can find the position of "19" in only three steps. However, as you see the array is already sorted.

    there are several sorting algorithms, if you want to learn ebout them, you can start with easy ones, such as selection sort, bubble sort or insertion sort. there are more complicated sort algorithms also such as quick sort, merge sort, radix sort or heap sort.

    Java platform uses a modified merge sort, and qick sort for its sort facilities. There are Arrays.sort() for arrays, and Collections.sort() for Lists available. But i got that you are in the learning phase, not sur eif you want to use them.

    Make a search in wikipedia about search algorithms or binary search, you can see several different implementations in various languages in the links area. Or Google it. For binary search or sort, you can also check how java is doing it by checking the source.
    hey thanks alot i managed it through bubble sort alghorithm :D


    thanks people :cool:

Similar Threads

  1. Can anybody help with cuncurrent binary search tree guys)
    By danylo in forum Threads and Synchronization
    Replies: 1
    Last Post: 04-23-2008, 06:22 PM
  2. Binary Search in Java
    By Java Tip in forum Algorithms
    Replies: 0
    Last Post: 04-15-2008, 07:43 PM
  3. Use recursion to convert binary to...
    By coco in forum Advanced Java
    Replies: 1
    Last Post: 08-07-2007, 07:46 AM
  4. problem with recursive binary search program
    By imran_khan in forum New To Java
    Replies: 3
    Last Post: 08-02-2007, 03:08 PM
  5. Binbot Binary Newsreader 1.1b3
    By levent in forum Java Software
    Replies: 0
    Last Post: 07-27-2007, 01:18 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •