力扣 704.二分查找 35.搜索插入位置34.查找元素位置 数组练习

二分查找

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-search

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left=0;
        int right=nums.size()-1;
        while(left<=right)
        {
            int mid=(left+right)/2;
            if(nums[mid]>target)
            {
                right=mid-1;//目标值比nums[mid]小，继续在数组左边寻找
            }
            else if(nums[mid]<target)
            {
                left=mid+1;//目标值比nums[mid]大，继续在数组右边寻找
            }
            else
            {
                return mid;
            }
        }
        return -1;
    }
};

搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

示例 1:

输入: [1,3,5,6], 5
输出: 2
示例 2:

输入: [1,3,5,6], 2
输出: 1
示例 3:

输入: [1,3,5,6], 7
输出: 4
示例 4:

输入: [1,3,5,6], 0
输出: 0

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/search-insert-position

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left=0;
        int right=nums.size()-1;
        while(left<=right)
        {
            int mid=(left+right)/2;
            if(nums[mid]>target)
            {
                right=mid-1;
            }
            else if(nums[mid]<target)
            {
                left=mid+1;
            }
            else
            {
                return mid;//找到目标值，返回索引
            }
        }
        if(left==-1&&target<nums[right])//当目标值应该插入到所有数字之前
        return 0;
        else if(left==nums.size()&&target>nums[right])//目标值插入到所有数字之后
        return right+1;//此时left>right，right+1=left
        else 
        return right+1;//目标值在数组中间插入
        

    }
};

查找元素的第一个和最后一个位置

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

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

示例 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]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int left=0;
        int right=nums.size()-1;
        int mid=(left+right)/2;
        while(right>=0&&left<=right)//注意0个元素的数组，不会进入循环
        {
            mid=(left+right)/2;
            if(target<nums[mid])
            {
                right=mid-1;
            }
            else if(target>nums[mid])
            {
                left=mid+1;
            }
            else
            {
                int i=mid;
                int j=mid;
                while(i>=0&&nums[i]==target)//当前位置往左寻找第一个目标值
                {
                    i--;
                }
                while(j<nums.size()&&nums[j]==target)//当前位置往右寻找最后一个目标值
                {
                    j++;
                }
                return {i+1,j-1};
            }
        }
        return {-1,-1};
      
    }
};