二分法——leetcode35. 搜索插入位置

叁歲伎倆 2022-11-06 08:59 164阅读 0赞

二分法的第一种写法  
在左闭右闭的区间寻找target；  
不变的量是：\[left,right\];

#include<bits/stdc++.h>
    using namespace std;
    int  binary_search(vector<int> &nums,int target)
    {
        
        int left = 0;
        int right = nums.size() - 1; //定义target在左闭右闭的区间里，[left,right];
    
        while (left <= right) //当left==right，区间[left,right]依然有效;
        {
        
             int mid = (left + right) / 2;
             if (target == nums[mid]) //关键的退出条件;
                 return mid;          //nums[mid]==target;
    
             if (target < nums[mid]) //target在左区间[left,mid-1];
                 right = mid - 1;
             else //target在右区间[mid+1,right];
                 left = mid + 1;
    
        }
        return right;//返回插入的位置
    }
       
    
    int main()
    {
        
        vector<int> vec = {
        1, 2, 3, 4, 5, 6, 7, 8, 9};
        cout << "输入要查询的数：" << endl;
        int n;
        cin >> n;
    
        cout << binary_search(vec, n);
        system("pause");
    
    }

二分法的第二种写法  
左闭右开的区间里去寻找target;  
不变量是\[left,right);

#include<bits/stdc++.h>
    using namespace std;
    
    int binary_search(vector<int> &nums,int target)
    {
        
        int left = 0;
        int right = nums.size(); //左闭右开的区间,[left,right);
        while (left < right)    //因为在left==right的时候，在[left,right);
        {
        
             int mid = (left + right) / 2;
             if (target == nums[mid]) //nums[mid]==target;
                 return mid;
             if (target < nums[mid]) //target在左区间，[left,mid);
                 right = mid;
             else
                 left = mid + 1; //target在右区间，[mid+1,right);
    
        }
        return right;
    
    
    }
    int main()
    {
        
        vector<int> vec = {
        1, 2, 3, 4, 5, 6, 7, 8, 9};
        cout << "输入要查询的数：" << endl;
    
        int n;
    
        cin >> n;
        cout << binary_search(vec, n);
        system("pause");
        return 0;
    }

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  
[35. 搜索插入位置][35.]

通过的代码

class Solution {
        
    public:
        int searchInsert(vector<int>& nums, int target) {
        
             int left = 0;
        int right = nums.size(); //左闭右开的区间,[left,right);
        while (left < right)    //因为在left==right的时候，在[left,right);
        {
        
             int mid = (left + right) / 2;
             if (target == nums[mid]) //nums[mid]==target;
                 return mid;
             if (target < nums[mid]) //target在左区间，[left,mid);
                 right = mid;
             else
                 left = mid + 1; //target在右区间，[mid+1,right);
    
        }
        return right;
    
        }
    };

[35.]: https://leetcode-cn.com/problems/search-insert-position/