LeetCode-中等进阶-34-在排序数组中查找元素的第一个和最后一个位置-二分法(C)

题目

给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target,返回 [-1, -1]。

进阶:

你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗?
 

示例 1:

输入:nums = [5,7,7,8,8,10], target = 8
输出:[3,4]
示例 2:

输入:nums = [5,7,7,8,8,10], target = 6
输出:[-1,-1]
示例 3:

输入:nums = [], target = 0
输出:[-1,-1]
 

提示:

0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums 是一个非递减数组
-109 <= target <= 109

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路

  • 用二分法来解决:
    • 对于取值的左边界来说,它是等于target,且前一个数小于target。
    • 同理,右边界等于target,且后一个数大于target。
    • 二分法找两次即可。
  • 这篇写的我难受,这是我改进后的算法,有点累,思路就写这些了,其余的都是特殊情况处理。

代码

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */

int binarySearch(int* nums, int left, int right, int target, bool isLeft);

int* searchRange(int* nums, int numsSize, int target, int* returnSize){
    int *returnArray = (int*)malloc(sizeof(int)*2);
    int i;
    *returnSize = 2;
    returnArray[0] = numsSize==0 ? -1 :((nums[0]==target) ? 0: binarySearch(nums, 0, numsSize-1, target, true));
    returnArray[1] = numsSize==0 ? -1 :((nums[numsSize-1]==target) ? numsSize-1 : (nums[returnArray[0]+1]!=target ? returnArray[0] :binarySearch(nums, returnArray[0], numsSize-1, target, false)));
    return returnArray;
}

int binarySearch(int* nums, int left, int right, int target, bool isLeft){
    int mid=(left+right)/2;
    if(isLeft){
            if(left>=right-1) {
                if(nums[right]==target) return right;
                else return -1;
            }
        else if(nums[mid] == target && nums[mid] < target) return mid;
        else if(nums[mid] >= target) return binarySearch(nums, left, mid, target, true);
        else return binarySearch(nums, mid, right, target, true);
    }
    else{
        if(left>=right-1) {
            if(nums[left]==target) return left;
            else return -1;
        }
        if(nums[mid+1] > target && nums[mid] == target) return mid;
        else if(nums[mid] <= target) return binarySearch(nums, mid, right, target, false);
        else return binarySearch(nums, left, mid, target, false);
    }
    return -1;
}

You may also like...

发表评论

邮箱地址不会被公开。 必填项已用*标注