binary search

[tranceluv]

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

[CaptainMorgan]

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.

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));
  }  
}

[tranceluv]

ah ok ic..

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

cheers

[CaptainMorgan]

Quote:

Originally Posted by tranceluv

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!

[afsina]

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

[tranceluv]

Quote:

Originally Posted by afsina

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

[afsina]

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.

[afsina]

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.

[tranceluv]

Quote:

Originally Posted by afsina

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

[afsina]

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.

[tranceluv]

Quote:

Originally Posted by afsina

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


thanks people