001    /*
002     * LAPIS lightweight structured text processing system
003     *
004     * Copyright (C) 1998-2002 Carnegie Mellon University,
005     * Copyright (C) 2003 Massachusetts Institute of Technology.
006     * All rights reserved.
007     *
008     * This library is free software; you can redistribute it
009     * and/or modify it under the terms of the GNU General
010     * Public License as published by the Free Software
011     * Foundation, version 2.
012     *
013     * LAPIS homepage: http://graphics.lcs.mit.edu/lapis/
014     */
015    
016    
017    package lapisx.util;
018    
019    /**
020     * Binary search routines.
021     */
022    public abstract class BinarySearch {
023        public static Debug debug = Debug.QUIET;
024    
025        /**
026         * Search a sorted array of integers.
027         * @param array Array of integers
028         * @param offset Starting offset of subarray to search
029         * @param length Length of subarray to search
030         * @param x Value to search for
031         * @return largest index i in subarray (offset <= i <= offset+length)
032         * such that all elements below i in the subarray are strictly less
033         * than x.  If x is found in the subarray, then array[i] == x (and i is
034         * the first occurence of x in the subarray).  If x is not found, 
035         * then array[i] is where x should be inserted in the sort order.
036         */
037        public static int search (int[] array, int offset, int length, int x) {
038            // handle 0-length subarray case right away
039            if (length <= 0)
040                return offset;
041    
042            int low = offset;
043            int high = offset+length-1;
044            // since length > 0, array[low] and array[high] are valid indices
045    
046            if (x <= array[low])
047                return low;
048            if (x > array[high])
049                return high+1;
050            
051            while (low+1 < high) {
052                // loop invariant: array[low] < x <= array[high],
053                //                 offset <= low < high < offset+length
054                int mid = (low + high)/2;
055                if (x <= array[mid])
056                    high = mid;
057                else
058                    low = mid;
059            }
060            // now we have array[low] < x <= array[high]
061            //             && (low+1 == high || low == high)
062            //  implies low+1 == high
063            debug.assertion (low+1 == high);
064            return high;
065        }
066    }