몇 가지 2 분. - 자바.

12826 단어 이분 찾기JavaTip
/**
 * 各种 二分
 * 相同key最小下标,最大下标
 * 小于key的最大下标
 * 大于key的最小下标
 * 数组升序排序, 找不到都返回-1
 *
 * @author: Guanpx [email protected]
 * @create: 2018-11-26 09:35:50
 **/
public class BinSearch {

    //查找相同key的最小下标
    //思路:向左一直找,最后的位置就是结果或者找不到
    public static int low_search(int[] arr, int key) {
        int l = 0;
        int r = arr.length - 1;    //下标减一
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (arr[mid] >= key) { //注意这种情况
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        if (l < arr.length && arr[l] == key) {
            return l;
        }
        return -1;
    }

    //查找相同key的最大下标
    public static int high_search(int[] arr, int key) {
        int l = 0;
        int r = arr.length - 1;    //下标减一
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (arr[mid] > key) {
                r = mid - 1;
            } else if (arr[mid] <= key) { //注意这种情况
                l = mid + 1;
            }
        }
        if (r >= 0 && arr[r] == key) {
            return r;
        }
        return -1;
    }

    // 小于当前k的最大下标值
    public static int small_search(int[] arr, int key) {
        int l = 0;
        int r = arr.length - 1;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (arr[mid] >= key) {
                r = mid - 1;
            } else
                l = mid + 1;
        }
        return r; //r会越界,变为-1,此情况直接返回
    }

    // 大于当前key的最小下标值
    public static int big_search(int[] arr, int key) {
        int l = 0;
        int r = arr.length - 1;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (arr[mid] > key) {
                r = mid - 1;
            } else if (arr[mid] <= key)
                l = mid + 1;
        }
        return l >= arr.length ? -1 : l; // 如果越界,即找不到大于key的,则返回-1
    }
}

좋은 웹페이지 즐겨찾기