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;
}