二分法总结

二分查找的前提有序数组且无重复元素， 如果有重复元素的话，会出现使用二分查找返回的元素下标不唯一的情况。

关于二分法的区间选择，可以查看二分法及C++之Vector容器。

LeetCode 704 二分查找

题目描述

给定一个 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      

提示：

- 你可以假设 nums 中的所有元素是不重复的。
- n 将在 [1, 10000]之间。
- nums 的每个元素都将在 [-9999, 9999]之间。

解法一：二分查找

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

            }
            return -1;
        } 
};

解法二：暴力解法

class Solution {   
public:
    int search(vector<int>& nums, int target) {
        int i;
        int a=nums.size()-1;
        for( i=0;i<=a;i++){
            if (nums[i]==target) {
                return i;
                break;   // break退出循环
            }
        }
      return -1;
    }
};

LeetCode 35 搜索插入位置

题目描述

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

请必须使用时间复杂度为 O(log n) 的算法。

示例1：

输入: nums = [1,3,5,6], target = 5
输出: 2

示例2：

输入: nums = [1,3,5,6], target = 2
输出: 1

示例3：

输入: nums = [1,3,5,6], target = 7
输出: 4

提示：

1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 为 无重复元素 的 升序 排列数组
-104 <= target <= 104

解题代码

 class Solution {
    public:
        int searchInsert(vector<int>& nums, int target) {
            int left=0;
            int right=nums.size()-1;
            while(left<=right){
                int middle=left+(right-left)/2;
                if (nums[middle]<target){
                    left=middle+1;
                }else if(nums[middle]>target){
                    right=middle-1;
                }else{
                    return middle;
                }
                }
            return right+1;    //注意此时要返回right+1
            }
    };

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

题目描述：

给你一个按照非递减顺序排列的整数数组nums，和一个目标值target。请你找出给定目标值在数组中的开始位置和结束位置. 如果数组中不存在目标值target，返回 [-1, -1]。 你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

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

解题思路：

寻找target在数组中的左右边界，有如下三种情况：

• 情况一： 数组元素target没有在数组中，此时返回（-1，-1）

• 情况二: 数组元素target在数组中,此时返回元素的第一个元素和最后一个元素

• 情况三： 数组元素target在数组范围中，但是不存在于数组中。

解题代码：

二分法

class Solution {
public:
    
    int Right=-2;
    int Left=-2;
    vector<int> searchRange (vector<int>& nums, int target) { 
        if(nums.size()==0) return{-1,-1};     // return 会退出函数 
        Right=FindRight(nums,target);
        Left=FindLeft(nums,target);
        // 如果数组中没有元素，那么返回（-1，-1）
        if(Right==-2||Left==-2) return{-1,-1};
        if(Right-Left>1) return{Left+1,Right-1};
        return{-1,-1};
    }

    int FindRight(vector<int>& nums, int target){
        int left=0;
        int right=nums.size()-1;
        while(left<=right){
            int middle=left+(right-left)/2;
            if (nums[middle]<=target){
                left=middle+1;
                Right=left;
            }else{
                right=middle-1;
            }
        }
        return Right;
    }

    int FindLeft(vector<int>& nums, int target){
        int left=0;
        int right=nums.size()-1;
        while(left<=right){
            int middle=left+(right-left)/2;
            if (nums[middle]>=target){
                right=middle-1;
                Left=right;
            }else{
                left=middle+1;
            }
        }
        return Left;
    }
};

对于情况二，会出现left=right的情况，不满足right-left>1的情况

暴力解法

LeetCode 69 x的平方根

题目描述：

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

示例1：

输入：x = 4
输出：2

输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。

解题思路

使用二分法求解时，引入一个temp变量，并用left+(right-left)/2作为middle, 最后的结果需要保证temp < x/middle

解法一： 二分法

class Solution {
public:
int left;
int right;
    int mySqrt(int x) {     
        if (x==0) return 0;
        if (x==1) return 1;
        if(x!=0 && x!=1) {
             left=0;
             right=x;
        while(left<=right){
           int middle=left+(right-left)/2;
            int temp=x/middle;        // 最后的结果是temp肯定不能比middle大
            if(temp<middle){
                right=middle-1;
            } else if(temp >middle){   //如果temp比middle大，说明需要增大middle，从而减小temp
                left=middle+1;
            } else if(temp==middle) {   //此时函数返回值是middle, 如果不相等的时候，也需要一个返回值。
            return middle; 
            }
        }
        }
        return right;   //此处也需要返回值以应对最后的temp不等于middle时没有返回值的情况
    } 
}

解法二： 牛顿迭代法

待补充