Binary search question...

[Maximilian]

I copied this from wikipedia:

int binary_search(int A[], int key, int imin, int imax)
{
  // test if array is empty
  if (imax < imin)
    // set is empty, so return value showing not found
    return KEY_NOT_FOUND;
  else
    {
      // calculate midpoint to cut set in half
      int imid = midpoint(imin, imax);
 
      // three-way comparison
      if (A[imid] > key)
        // key is in lower subset
        return binary_search(A, key, imin, imid-1);
      else if (A[imid] < key)
        // key is in upper subset
        return binary_search(A, key, imid+1, imax);
      else
        // key has been found
        return imid;
    }
}

I don't know that language but i recognize the jist of whats going on, correct me if im wrong but wont this fail if key is higher than any value in the array?

 

[BrightCandle]

Why don't you copy it, modify it and create a test and see what it does. Its probably C code but it looks like it would largely work in Java as well with a few minor tweaks.

 

[Maximilian]

I did and it dosent seem to take account for it. I just ask because im not too confident with this stuff yet and maybe i missed something in how the wikipedia code works.

 public static int recursiveBinarySearch(int[] intArray, int valueToFind, int minIndex, int maxIndex)
    {
        int midIndex = getMid(minIndex,maxIndex);

        recursionCounter++;

        if (valueToFind > intArray[midIndex] && midIndex != intArray.length-1)
        {
            System.out.println("Current mid index " + midIndex);
            System.out.println("Current min index " + minIndex);
            return recursiveBinarySearch(intArray, valueToFind,midIndex+1,maxIndex);
        }
        else
        {
            if (valueToFind < intArray[midIndex] && midIndex != 0)
            {
                return recursiveBinarySearch(intArray, valueToFind,minIndex,midIndex-1);
            }
            else
            {
                if (valueToFind == intArray[midIndex])
                {
                    return midIndex;
                }
                else
                {
                    return -1;
                }
            }
        }
    }

Thats my implementation, works for values actually in the array or values smaller/larger than anything in the array but will infinite loop on values between the smallest and largest in the array but are not actually present. Still tinkering with it

 

[Jaydip]

I did and it dosent seem to take account for it. I just ask because im not too confident with this stuff yet and maybe i missed something in how the wikipedia code works.

 public static int recursiveBinarySearch(int[] intArray, int valueToFind, int minIndex, int maxIndex)
    {
        int midIndex = getMid(minIndex,maxIndex);

        recursionCounter++;

        if (valueToFind > intArray[midIndex] && midIndex != intArray.length-1)
        {
            System.out.println("Current mid index " + midIndex);
            System.out.println("Current min index " + minIndex);
            return recursiveBinarySearch(intArray, valueToFind,midIndex+1,maxIndex);
        }
        else
        {
            if (valueToFind < intArray[midIndex] && midIndex != 0)
            {
                return recursiveBinarySearch(intArray, valueToFind,minIndex,midIndex-1);
            }
            else
            {
                if (valueToFind == intArray[midIndex])
                {
                    return midIndex;
                }
                else
                {
                    return -1;
                }
            }
        }
    }

Thats my implementation, works for values actually in the array or values smaller/larger than anything in the array but will infinite loop on values between the smallest and largest in the array but are not actually present. Still tinkering with it

Remember Binary search requires the data to be sorted

 

[Maximilian]

Remember Binary search requires the data to be sorted

Yeah it was sorted but if someArray consisted of [2,4,6,8,10,12] and i searched for 5 it will crash.

I figured two solutions.

Bad solution (tell me if this is lousy practice because it seems like it may be :whiste plan for the stack overflow exception my code will throw in that case with a try/catch/finally and have the finally clause return -1

Better solution, if the current midIndex is the same as the previous mixIndex value (stored in a static variable) then return -1, because that's the start of an infinite loop. This seems to work, haven't been able to crash it yet:

    public static int recursiveBinarySearch(int[] intArray, int valueToFind, int minIndex, int maxIndex)
    {
        int midIndex = getMid(minIndex,maxIndex);
        recursionCounter++;
        System.out.println("Current mid index " + midIndex);
        System.out.println("Current min index " + minIndex);
        System.out.println("Current max index " + maxIndex);
        System.out.println("-------------------------------");
        if (midIndex == previousMidIndex)
        {
            return -1;      
        }
        else
        {
            if (valueToFind > intArray[midIndex] && midIndex != intArray.length-1)
            {
                previousMidIndex = midIndex;
                return recursiveBinarySearch(intArray, valueToFind,midIndex+1,maxIndex);
            }
            else
            {
                if (valueToFind < intArray[midIndex] && midIndex != 0)
                {
                    previousMidIndex = midIndex;
                    return recursiveBinarySearch(intArray, valueToFind,minIndex,midIndex-1);
                }
                else
                {
                    if (valueToFind == intArray[midIndex])
                    {
                        return midIndex;
                    }
                    else
                    {
                        return -1;
                    }
                }
            }        
        }
    }

 

[Leros]

Here is the actual implementation from java.util.Arrays

    // Like public version, but without range checks.
    private static int binarySearch0(double[] a, int fromIndex, int toIndex,
                                     double key) {
        int low = fromIndex;
        int high = toIndex - 1;

        while (low <= high) {
            int mid = (low + high) >>> 1;
            double midVal = a[mid];

            if (midVal < key)
                low = mid + 1;  // Neither val is NaN, thisVal is smaller
            else if (midVal > key)
                high = mid - 1; // Neither val is NaN, thisVal is larger
            else {
                long midBits = Double.doubleToLongBits(midVal);
                long keyBits = Double.doubleToLongBits(key);
                if (midBits == keyBits)     // Values are equal
                    return mid;             // Key found
                else if (midBits < keyBits) // (-0.0, 0.0) or (!NaN, NaN)
                    low = mid + 1;
                else                        // (0.0, -0.0) or (NaN, !NaN)
                    high = mid - 1;
            }
        }
        return -(low + 1);  // key not found.
    }

Source:
http://grepcode.com/file/repository...ava#Arrays.binarySearch0(long[],int,int,long)

 

[esun]

Yeah it was sorted but if someArray consisted of [2,4,6,8,10,12] and i searched for 5 it will crash.

I tried this out and it worked fine (made a python version). So we have:

A = [2, 4, 6, 8, 10, 12]
key = 5
imin = 0
imax = 5

So let's go through the iterations (just going to print imin, imax, imid on each iteration, where imid = (imin + imax)/2):

0 5 2
0 1 0
1 1 1
key not found

#!/usr/bin/python

def binary_search(A, key, imin, imax):
    if imax < imin:
        return "key not found"
    else:
        imid = (imin + imax) / 2
        if A[imid] > key:
            return binary_search(A, key, imin, imid-1)
        elif A[imid] < key:
            return binary_search(A, key, imid+1, imax)
        else:
            return imid

A = [2, 4, 6, 8, 10, 12]

print binary_search(A, 5, 0, len(A)-1)

Wow I just looked at your Java code and it is VERY different from the Wikipedia code. Did you mean to implement Wiki code in Java or was it meant to be your own implementation? (I guess I'm not sure whether you're asking if there's a bug in the Wiki code, your code, or the translation between the Wiki code and your code.)

 

[Maximilian]

Yeah that's my own implementation, i was looking to code a binary search and learning how to do it by looking at the stuff on wiki etc.

I never thought the wiki code had a bug just that it didn't seem to account for not finding the value, or at least i couldn't visualize how it would do so.

Ohh i seee it!! Following through the values one at a time on the final iteration iMin will become 2 and iMax will be 1 therefore the base condition will actually fire and it will return not found... yeah! So i was missing something about the code Thanks for that esun.