二分查找与分治算法

算法的复杂度跟递归不递归没有关系，跟怎么设计代码有关

二分查找是从已排序的数组中进行查找，查找一个元素时间复杂度Log(n)，查找n的元素时间复杂度nlog(n)

二分查找的递归实现
//二分查找
#include<stdio.h>
bool binary_search(std::vector<int>&sort_array,int begin,int end,int target)
{
	if(end<begin){
		return false;
		}
	int mid=(begin+end)/2;
	if(target==sort_array[mid])
	{
		return mid;
	}
	else if(target<sort_array[mid]){
		return binary_search(sort_array,begin,mid-1,target);
	}
	else if(target>sort_array[mid]){
		
		return binary_search(sort_array,mid+1,end,target);
	}
} 
二分查找的循环实现
bool binary_search_loop(std::vector<int>&sort_array,int target){
	int begin=0;
	int end=sort_array.size()-1;
	while(begin<=end){
		int mid=(begin+end)/2;
		if(target==sort_array[mid]){
			return true;
		}
		else if(target<sort_array[mid]){
			end=mid-1;
		}else if(target>sort_array[mid]){
			begin=mid+1
		}
	}
	return false;
}
LeetCode 34 Search Insert Position插入位置
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int index=-1;
        int begin=0;
        int end=nums.size()-1;
        while(index==-1){
            int mid=(begin+end)/2;
            if(target==nums[mid]){
                index=mid;
            }
            else if(target<nums[mid]){
                if(mid==0||target>nums[mid-1]){
                    index=mid;
                }
                end=mid-1;
            }
            else if(target>nums[mid]){
                if(mid==nums.size()-1||target<nums[mid+1]){
                    index=mid+1;
                }
                begin=mid+1;
            }
        }
        return index;
        
    }
};

LeetCode34区间查找Search for a range
class Solution {
public:
    int left_bound(std::vector<int>&nums,int target){
        int begin=0;
        int end=nums.size()-1;
        while(begin<=end){
            int mid=(begin+end)/2;
            if(target==nums[mid])
            {
                if(nums[mid-1]<target||mid==0)
                {
                    return mid;
                }
                end=mid-1;
               
            }else if(target<nums[mid]){
                end=mid-1;
            }
            else if(target>nums[mid]){
                begin=mid+1;
            }
        }
        return -1;
    }
    int right_bound(std::vector<int>&nums,int target){
        int begin=0;
        int end=nums.size()-1;
        while(begin<=end){
            int mid=(begin+end)/2;
            if(target==nums[mid])
            {
                if(nums[mid+1]>target||mid==nums.size()-1)
                {
                    return mid;
                }
                begin=mid+1;
               
            }else if(target<nums[mid]){
                end=mid-1;
            }
            else if(target>nums[mid]){
                begin=mid+1;
            }
        }
        return -1;
    }
    vector<int> searchRange(vector<int>& nums, int target) {
        int left=left_bound(nums,target);
        int right=right_bound(nums,target);
        std::vector<int>res;
        res.push_back(left);
        res.push_back(right);
        return res;
        
    }
};
LeetCode33旋转数组查找 Search in Rotated Sorted Array
//代码没写

（1）将两个有序数组合并成一个有序数组
（2）归并排序：将乱序数组排序
首先将规模分成k个子问题，在子问题上排序后再合并
步骤：
分解：分解成子问题
求解：子问题较简单的时候求解
合并：子问题逐层合并
归并排序复杂度：o(nlogn)
归并排序代码：
void merge_two_vec(std::vector<int>&subvec1,std::vector<int>&subvec2,std::vector<int>&vec)
{
}
void merge_sort(std::vector<int>&vec)
{
if(vec.size()==1)
{
return;
}
int mid=vec.size()/2;
std::vector<int>sub_vec1;
std::vector<int>sub_vec2;
for(int i=0;i<mid;i++)
{
sub_vec1.push_back(vec[i]);
}
for(int i=mid;i<vec.size();i++)
{
sub_vec2.push_back(vec[i]);
}
merge_sort(sub_vec1);
merge_sort(sub_vec2);
vec.clear();
merge_sort_two_vec(sub_vec1,sub_vec2,vec);
}