// CSE 143, Winter 2009
//
// This class provides a binarySearch method for searching a sorted array of ints.
// You do NOT need to use this file unless you have an older Mac and are not able
// to successfully upgrade it to Java v1.6.  We strongly recommend that you try
// upgrading your Java to v1.6 by following the Mac JDK download link on the
// course web site before using this file.
//
// NOTE: Even if you use this file, you will still need to import java.util.*;
// in your SortedIntList program.  If you do not, you may lose points because
// your program may not compile when we run it on our testing server.
//
// author: Stuart Reges, 1/11/08   (minor modifications by Marty Stepp 1/11/09)

public class Arrays {
    // Returns the index of the given key in the list within the range
    // fromIndex (inclusive) through toIndex (exclusive); returns
    // (-(insertion point) - 1) otherwise.  The insertion point is
    // defined as the point at which the key would be inserted into the
    // array: the index of the first element in the range greater than
    // the key, or toIndex if all elements in the range are less than the
    // specified key.  Note that this guarantees that the return value
    // will be >= 0 if and only if the key is found.  If the list
    // contains multiple copies of the key in the given range, there is
    // no guarantee which index is returned.
    //
    // Precondition: elements in indexes fromIndex (inclusive)
    // to toIndex (exclusive) are in sorted (nondecreasing) order
    public static int binarySearch(int[] list, int fromIndex, int toIndex, int key) {
        int low = fromIndex;
        int high = toIndex - 1;
    
        while (low <= high) {
            int mid = (low + high) / 2;
            int midVal = list[mid];
    
            if (midVal < key) {
                low = mid + 1;
            } else if (midVal > key) {
                high = mid - 1;
            } else {
                return mid;  // key found
            }
        }
        return -(low + 1);   // key not found
    }
}