Binary Search Help

[a22asin]

Hi, i found this code in my textbook for binary search, but i dont quite understand how it works:

code:

public static int binarySearch(int[] array, int value){                 int low = 0;                 int high = array.length-1;                 int count = 0;                                 while(low <= high){                         count++;                         int mid = (low + high) / 2;                         if(value < array[mid]){                                 high = mid - 1;                         }else if(value > array[mid]){                                 low = mid + 1;                         }else{                                 return mid;                         }                 }                 return -1;

[/code]

[evildaddy911]

did you try googling "binary search"?

basically, the algorithm for binary searching is to take a sorted array and a value that should be in the array. then you take the middle element of the array and compare it to the "value" parameter. if it is greater, discard the lower half and repeat until the middle element is equal to value. typically, binary searches are recursive, but this one defines minimum and maximum elements for the search to do it in-place. the method takes the midpoint of the min/max elements and uses that instead of the array's middle element

breakdown:
parameters: sorted array, value to find
1) define default min/max elements (0 and length -1)
-- loop --
2) define midpoint ((max - min) / 2)
3) if array [midpoint] equals "value", return; otherwise, redefine the min/max elements accordingly
-- end loop --

[Raknarg]

I'll try to clear this up.

So a binary search works like a number game. Lets say you need to guess a number between 1 and 100, and you have 5 guesses. What's the best approach? First, you pick 50. That number is too low, whats the next best guess? 75. That's too high. 62? too high. 56? too low. 59? You got it right.

What I did there was just the fastest way to guess the number. Now lets try to apply it mroe to this code.

You have your paramters, high and low. In this case, low = 1 and high = 100. We need to guess a randomly selected number inside that range.

Smartest way to begin is pick the number that is halfway between 1 and 100, ie low and high. That number is 50, but it's too low.

Now this is what we do: We know that every number less that 50 is not right, so we can set our new low to 50. Cool, we just halved the amount of work!

Lets try it again. What is in between 50 and 100? 75. SO we guess 75. However, that is too high. Now we know everything greater than 75 is not right, so we can set our new high to 75. Wee keep doing this until we approach our desired number, 59.

Now here's what this program is doing: It takes in an array of SORTED values. This is important, because it only works when everything in the list is sorted. It It picks the number in the middle of the list. Is it our number? If not, is it higher or lower? If it's too low, we know that everything under the middle of the list is also not right, so we can move our lower point up to the middle. Opposite holds true if it's too high.

Eventually, it reaches the desired number, and the result tells you the position of the number given. If it's not in the array, it gives you a -1(none of the positions).

The cool thing about this is that it's way faster than searching through everything in the array. If you took 1000 numbers, and looked through each number one by one, it could take 1000 iterations to find the right number. However, with this binary search, it is guaranteed to find it in log1000(I think) steps, which in this case is about 10.

EDIT: @evildaddy don't forget that if you don't have to do a problem recursively, it's better not to, unless it's way easier to do do. FOr instance, if you programmed a Fibbonacci number generator recursively in python with n > 9000, it would crash because you'll get a run time error. If you do it without recursion, it doesn't waste so much data and works fine

[evildaddy911]

no you dont have to do everything recursively.
however, i feel that in this case, recursion can make the algorithm much clearer (assuming you understand recursion, i know my programming teacher doesn't).

yeah, the major downside to recursion is the memory space it requires, but in terms of speed and clarity (again, assuming you understand recursion), in my mind at least, it tends to be superior

[Raknarg]

It really just depends on the case. As long as it's working in some form of logn time, it's usually ok.