代码随想录

34. 在排序数组中查找元素的第一个和最后一个位置

34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）

#include<stdio.h>
#include<stdlib.h>
int* searchRange(int* nums, int numsSize, int target);

int main() {
	int nums[6] = { 5,7,7,8,8,10 };
	int numsSize = 6, target = 6;
	int *p = searchRange(nums, numsSize, target);
	for (int i = 0; i < 2; i++) {
		printf("%d ", *(p+i));
	}
}
int* searchRange(int* nums, int numsSize, int target) {
	int* ans = (int*)(malloc(sizeof(int) * 2));
	int first, last;
	first = -1;
	last = -1;
	int low = 0, high = numsSize - 1, mid;
	//找到第一次target的位置
	while (low <= high) {
		mid = (low + high) / 2;
		if (nums[mid] > target) {
			high = mid - 1;
		}
		else if (nums[mid] < target) {
			low = mid + 1;
		}
		else {
			first = mid;
			high = mid - 1;//接下来去[low,mid-1]范围内去找还有没有target
		}
	}
	//找到最后一次target的位置
	low = 0, high = numsSize - 1;
	while (low <= high) {
		mid = (low + high) / 2;
		if (nums[mid] > target) {
			high = mid - 1;
		}
		else if (nums[mid] < target) {
			low = mid + 1;
		}
		else {
			last = mid;
			low = mid + 1;//接下来去[mid+1,high]范围内去找还有没有target
		}
	}
	if (first == -1) {
		ans[0] = -1;
		ans[1] = -1;
	}
	else {
		ans[0] = first;
		ans[1] = last;
	}
	return ans;
}

可以运行

代码成功通过力扣

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int>ans={-1,-1};
        int first, last;
        first = -1;
        last = -1;
        int low = 0, high = nums.size() - 1, mid;
        //找到第一次target的位置
        while (low <= high) {
            mid = (low + high) / 2;
            if (nums[mid] > target) {
                high = mid - 1;
            }
            else if (nums[mid] < target) {
                low = mid + 1;
            }
            else {
                first = mid;
                high = mid - 1;//接下来去[low,mid-1]范围内去找还有没有target
            }
        }
        //找到最后一次target的位置
        low = 0, high = nums.size()  - 1;
        while (low <= high) {
            mid = (low + high) / 2;
            if (nums[mid] > target) {
                high = mid - 1;
            }
            else if (nums[mid] < target) {
                low = mid + 1;
            }
            else {
                last = mid;
                low = mid + 1;//接下来去[mid+1,high]范围内去找还有没有target
            }
        }
        if (first != -1) {
            ans.pop_back();
            ans.pop_back();
            ans.push_back(first);
            ans.push_back(last);
        }
        return ans;
        }
};