【剑指offer】搜索篇-含题目代码思路解析

class Solution {
public:
    int bisearch(vector<int>& data,float k){
        int left=0;
        int right=data.size()-1;
        while(left<=right){
            int mid=(left+right)/2;
            if(data[mid]<k){
                left=mid+1;
            }else if(data[mid]>k){
                right=mid-1;
            }
        }
        return left;
    }
    int GetNumberOfK(vector<int> data ,int k) {
        return bisearch(data,k+0.5)-bisearch(data, k-0.5);
    }
};

class Solution {
public:
    bool binary_search(int target,vector<int>array){
        int left=0;
        int right=array.size()-1;
        while(left<=right){
            int mid=(left+right)/2;
            if(array[mid] == target)return true;
            else if(array[mid]<target){left=mid+1;}
            else if(array[mid]>target){right=mid-1;}
        }
        return false;
    }
    bool Find(int target, vector<vector<int> > array) {
        for(auto i:array){
            if(binary_search(target, i))return true;
        }
        return false;
    }
};

int arr[] = {1, 2, 3};  
for(auto i : arr) {  
     std::cout<< i << std::endl;  
}  

class Solution {
public:
    int binary_search(vector<int> array){
        int left=0;
        int right=array.size()-1;
        while(left<right){
            int mid=(left+right)/2;
            if(array[mid]>array[right]){left=mid+1;}
            else if(array[mid]<array[right]){right=mid;}
            else if(array[mid]==array[right]){right--;}
        }
        return array[right];
    }
    int minNumberInRotateArray(vector<int> rotateArray) {
       return binary_search(rotateArray);
    }
};

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return int整型
     */
    int findNthDigit(int n) {
        int digits=1;
        long long  sum=9;
        while(n>sum){
            n-=sum;
            sum=pow(10,digits-1);
            digits++;
            sum=9*sum;
        } 
        int num =pow(10,digits-1)+ (n - 1) / digits;
           printf("%lld hhhh",sum);
        //定位n在数字的哪一位上
        int index = (n - 1) % digits;
        return to_string(num)[index] - '0';
    }
};