# 2303. Calculate Amount Paid in Taxes
###### tags: `Leetcode` `Easy`
Link: https://leetcode.com/problems/calculate-amount-paid-in-taxes/description/
## 思路
一开始的想法是用binary search 但其实完全不能节省时间复杂度
因为还是要把前面的所有元素遍历一遍
## Code
正确写法 O(N)

class Solution {
    public double calculateTax(int[][] brackets, int income) {
        int prev = 0;
        double ans = 0;
        for(int[] b:brackets){
            if(income>=b[0]){
                ans += (b[0]-prev)*b[1]/100d;
                prev = b[0];
            }
            else{
                ans += (income-prev)*b[1]/100d;
                break;
            }
        }
        return ans;
    }
}

binary search O(N)

class Solution {
    public double calculateTax(int[][] brackets, int income) {
        int l=0, r=brackets.length;
        while(l<r){
            int mid = l+(r-l)/2;
            if(brackets[mid][0]<income) l = mid+1;
            else r = mid;
        }
        double ans=0;
        for(int i=0; i<l; i++){
            ans += (double)((brackets[i][0]-(i!=0?brackets[i-1][0]:0))*brackets[i][1])/100;
        }
        ans += (double)((income-(l!=0?brackets[l-1][0]:0))*brackets[l][1])/100;
        return ans;
    }
}