要么改变世界,要么适应世界

算法模板之二分查找

2020-08-24 19:23:00
134
目录

二分查找应用于在有序数组中寻找满足特定条件的元素,时间复杂度可以降到O(logn),该算法的必要前提是有序数组必须有序。

查找不小于target元素的下标

int lower_bound(int[] nums, int start, int end, int target) {
    int mid = 0;
    while (start < end) {
        mid = (start + end) / 2;
        if (target > nums[mid]) {
            start = mid + 1;
        } else {
            end = mid;
        }
    }
    if (nums[end] < target) return -1;
    return end;
}

查找大于target元素的下标

int upper_bound(int[] nums, int start, int end, int target) {
    int mid = 0;
    while (start < end) {
        mid = (start + end) / 2;
        if (target >= nums[mid]) {
            start = mid + 1;
        } else {
            end = mid;
        }
    }
    if (nums[end] < target) return -1;
    return end;
}

查找第一个target元素的下标

int exist_bound(int[] nums, int start, int end, int target) {
    int mid = 0;
    while (start < end) {
        mid = (start + end) / 2;
        if (target > nums[mid]) {
            start = mid + 1;
        } else if (target < nums[mid]) {
            end = mid - 1;
        } else {
            if (mid - 1 < 0) {
                return 0;
            } else if (nums[mid - 1] == target) {
                end = mid - 1;
            } else {
                return mid;
            }
        }
    }
    if (end < 0 || nums[end] != target) return -1;
    return end;
}
历史评论
开始评论