首页 > 代码库 > 爪哇国新游记之二十七----数组的二分查找

爪哇国新游记之二十七----数组的二分查找

代码:

import java.util.ArrayList;import java.util.List;public class Bit {    int max;    int min;    int[] arr;    public Bit(int[] arrInput) {        // 找出极值        for (int i = 0; i < arrInput.length; i++) {            if (max < arrInput[i]) {                max = arrInput[i];            }            if (min > arrInput[i]) {                min = arrInput[i];            }        }        // 新建数组        arr = new int[max - min + 1];        // 数组插值        for (int i : arrInput) {            int index = i - min;            arr[index]++;        }    }    public boolean hasDuplicateItem() {        for (int i = 0; i < arr.length; i++) {            int value =http://www.mamicode.com/ arr[i];            if (value > 1) {                return true;            }        }        return false;    }    public List<Integer> getSortedList() {        List<Integer> ls = new ArrayList<Integer>();        for (int i = 0; i < arr.length; i++) {            int value =http://www.mamicode.com/ arr[i];            if (value != 0) {                for (int j = 0; j < value; j++) {                    ls.add(min + i);                }            }        }        return ls;    }    public List<Integer> getUniqueSortedList() {        List<Integer> ls = new ArrayList<Integer>();        for (int i = 0; i < arr.length; i++) {            int value =http://www.mamicode.com/ arr[i];            if (value != 0) {                ls.add(min + i);            }        }        return ls;    }        public int[] getUniqueSortedArray(){        List<Integer> ls=getUniqueSortedList();                int[] arr=new int[ls.size()];                for(int i=0;i<arr.length;i++){            arr[i]=ls.get(i);        }                return arr;    }    /**     * 二分查找     *      * @param sortedArray     *            已排序的欲查找的数组     * @param seachValue     *            查找的值     * @return 找到的元素下标,若找不到则返回-1     */    public static int binSearch(int[] sortedArray, int seachValue) {        // 左边界        int leftBound = 0;        // 右边界        int rightBound = sortedArray.length - 1;        // 当前下标位置        int curr;        while (true) {            // 定位在左边界和右边界中间            curr = (leftBound + rightBound) / 2;            if (sortedArray[curr] == seachValue) {                // 找到值                return curr;            } else if (leftBound > rightBound) {                // 左边界大于右边界,已经找不到值                return -1;            } else {                if (sortedArray[curr] < seachValue) {                    // 当当前下标对应的值小于查找的值时,缩短左边界                    leftBound = curr + 1;                } else {                    // 当当前下标对应的值大于查找的值时,缩短右边界                    rightBound = curr - 1;                }            }        }    }    public static void main(String[] args) {        int[] arr = { -2, -1, 3, 5, 7, 9, 30, 4, -2, 5, 8, 3 };        Bit b = new Bit(arr);        System.out.println("排序后数组");        int[] arr2=b.getUniqueSortedArray();        for(int i=0;i<arr2.length;i++){            System.out.println(i+":"+arr2[i]);        }                int[] arr3={2,5,7,-2,90};                for(int i=0;i<arr3.length;i++){            int index=Bit.binSearch(arr2, arr3[i]);            if(index!=-1){                System.out.println(arr3[i]+"排在数组arr2的第"+index+"个");            }else{                System.out.println(arr3[i]+"不在数组arr2中");            }        }    }}

输出:

排序后数组0:-21:-12:33:44:55:76:87:98:302不在数组arr2中5排在数组arr2的第4个7排在数组arr2的第5个-2排在数组arr2的第0个90不在数组arr2中