[数据结构与算法]LeetCode——二分查找(704. 二分查找278. 第一个错误的版本35. 搜索插入位置)

练习题目

题解

704. 二分查找

class Solution {
public:
    int search(vector<int>& a, int target) {
        int len=a.size();
        int l=0,r=len-1;
        int m=0;
        while(l<=r)
        {
            m=l+(r-l)/2;
            if(a[m]==target)
            return m;
            else if(a[m]>target)
            r=m-1;
            else if(a[m]<target)
            l=m+1;
        }
        return -1;
    }
};

278. 第一个错误的版本

// The API isBadVersion is defined for you.
// bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {
        int l=1,r=n;
        int m=0;
        while(l<r)
        {
            m=l+(r-l)/2;
            if(isBadVersion(m))
            r=m;
            else
            l=m+1;
        }
        return l;
    }
};

35. 搜索插入位置

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