1. Member
Join Date
Jan 2008
Posts
5
Rep Power
0

## 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]; ...

2. 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));
}
}```

3. Member
Join Date
Jan 2008
Posts
5
Rep Power
0
ah ok ic..

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

cheers

4. 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!

5. Member
Join Date
Jan 2008
Posts
24
Rep Power
0
i am assuming you are doing binary search code because you want to practice. Because obviously Arrays.binarySearch(...) does the thing.

6. Member
Join Date
Jan 2008
Posts
5
Rep Power
0
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

7. Member
Join Date
Jan 2008
Posts
24
Rep Power
0
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. Member
Join Date
Jan 2008
Posts
24
Rep Power
0
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. Member
Join Date
Jan 2008
Posts
5
Rep Power
0
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

10. Member
Join Date
Jan 2008
Posts
24
Rep Power
0
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. Member
Join Date
Jan 2008
Posts
5
Rep Power
0
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 :D

thanks people :cool:

#### Posting Permissions

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