力扣每日一题-第46天-704. 二分查找

2022.7.30今天你刷题了吗？

---

题目：

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

分析：

给定一个升序数组和整型，在这个数组中找到是否存在这个整型，存在则返回下标，不存在则返回-1。

思路：对于查找问题：第一思路就是二分查找。利用两个下标一左一右，分别从两端开始。判断中间的值是否和目标一样，根据大小关系调整下标。

当target>num，则说明目标值在num右边，则left变

当target<num，则说明目标值在num左边，则right变

解析：

1.二分法

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        
        while (left <= right)
        {
            int mid = (right - left) / 2 + left;
            int num = nums[mid];
            if (target > num)
            {
                left = mid + 1;
            }
            else if (target < num)
            {
                right = mid - 1;
            }
            else
            {
                return mid;
            }

        }
        return -1;
    }
};

2.暴力法

直接对数组进行遍历，当遍历的元素小于target一直遍历，当出现相等则返回下标，当出现大于情况则返-1

class Solution {
public:
    int search(vector<int>& nums, int target) {
    int i=0;
    while(i<nums.size()-1&&nums[i]<target)
    {
        i++;
    }
    if(nums[i]!=target)
    {
        i=-1;
    }
    return i;
    }
};