Algorithm(11) Binary search

The questions related to binary search.

Input data	Basic(unique, exact target, one sorted array)	Multiple sorted subarray(peak,mountain)	Repeated element	Close to the target (two variables)
SingleNumber	TBD
Array	35,34,704	33,153,162,852	81,154	69,875,1011,74
Matrix	74

Useful tips:

• Divide and conquer (D&C) is not an algorithm but algorithm design paradigm used by Binary search algorithm. The only difference is that in binary search we discard half of the remaining elements at each iteration, whereas in most other D&C problems, we don’t discard any elements. For example, the merging sort is famouse divide and conqure approach, we divede the work space into several small parts and then merge results back. In some dp related question, we can also find this pattern easily. The start point is considering how this problem can be formed by solving a smaller scale problem.

• 注意使用binary search 的前提，在有序序列的基础上，通过binary search可以减少时间复杂度，从O(n)的复杂度降低到O(logn)，一看到O(logn)的复杂度的要求，一个标记就是binary search

• The basic thing is to write the binary search template quickly, there are multiple syle, just remember one in mind. in while loop, the comparision is left<=right, it is important to add = here, since left and right pointer can move to the same position, when they overlap with each other, just return the mid value. There are three cases here

while (left <= right){
mid = (left + right) / 2;
if (array[mid]==val){return mid}
else if (array[mid]<val){left=mid+1}
else //(array[mid]>val){right=mid-1}
}
return left or not find (the left and right pointer is switched here)

Why this template work:

Assuming the array value equals to their index value. If the left is n, right is n+1, there are three cases:

Case 1, target is n, the value of (l+r)/2=n is the correct position (namely the n), we can find element.

Case 2, target is n+1, (l+r)/2=n, mid<target, move left from n to n+1, than (l+r)/2 = n+1, target is found.

Attention for the Case 3, the template dose not work well in this case. Assuming the target is a value between n and n+1, such as n+0.5, (l+r)/2=n, the return value is smaller than the target value, left pointer still move from n to n+1, the return value of next time is n+1 which is larger than the target, then the right pointer moves from n+1 to n, then the condition in while loop is broken, left pointer is at value n and right pointer is at value n+1. In this case, when we return the left value, it is the first element that has a value larger than target value. If we want to approach the target from the left side, we need to return left-1 or just right index in this case when the condition is broken

• The case where there are multiple array elements having same values. Another typical patten of the binary search framework is to consider the case when there are multiple elements have same value, for example the 378, it requires us to return leftmost elements when there are multiple elements have same value, in this case, we need to merge the condition when the element equals to target and smaller than target. When the condition is broken, if the element exists, we can return current L, otherwise, we can reutrn -1, this is a simple example:

int test2(int *array, int len, int t)
{

    int l = 0;
    int h = len - 1;
    while (l <= h)
    {
        int m = (l + h) / 2;
        if (array[m] == t)
        {
            h = m - 1;
        }
        else if (array[m] < t)
        {
            l = m + 1;
        }
        else
        {
            // array[m]>t
            h = m - 1;
        }
    }
    //current l is the leftmost elements for subarray with equal values
    //if multiple elements have same value, and we also found it
    if (array[l] == t)
    {
        return l;
    }
    // not find
    return -1;
}

• Be careful about the difference between binary search and “divide and conqure” Binaray search is a kind of special use case of divide and conqure, the thought of divide and conqure can be used widely. The most classic case for the divide and conqure is the merge sort or quick sort. The proof about why binary based approach has log(NLogN) complexity. If we use merge sort as a example, and use F(N) to represent the time complexity, after using divide and conqure, there is F(N) = 2F(N/2)+KN, the K is a constant, since number since we need to do the merge operation after each divide operation. This is a nature way to write a function in a recursive pattern. If we continue replace the F(N/2), there is F(N)=2^2F(N/(2^2))+2KN, the total layer we can do in a recursive way is logN, so the final results is 2^(logN)F(1)+logN(KN), if the base is 2, the 2^(logN) equals to N, so the final time complexity is O(NlogN). So with the divide and conqure strategy, there is no way to decrease the complexity to a smaller number than N. The difference for the binary search case is to (1) decrease the scale of the subproblem by comparing it with mid element, (2) besides, there is also some other requirement, such as sorted input array. In the binary search case, there is F(n)=K+F(n/2) the K is constant to decide if we need to go to left or right branch (we can do this since array is sorted) Then there is F(n/2) = K+F(n/4), finally, we have F(n) = K logN + F(1) There is logN level in total to divide the sequence from N to 1. That is why the complexity can be O(logN), which is different with the divide and conqure scenario for the merging sort which needs to go through both branch in each recursion and there is linear time for each merging operation.

• Multiple sorted array is a typical estension in this part, just be careful about the case where there are repeated elements, in this case, just move one element.

• For searching the matrix, we need to update the i and j at the same time. The condition is different to the 1d case (l<r)

Recursive style

35 This is the standard binary search question, it can be also written in a form of while loop (since in each iteration, we have a clear idea about move to left or move to right branch), when start position value is larger than end position value, the condition is broken and we can not find the value, we want a position where we can insert it, this is tricky, assuming the current list is [3,5] we want insert 4, the when the start position moves to element 5(index 1), we break the loop, this is also the position we want to insert 4, so we return s in this case.

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        return bsearch(0,nums.size()-1,nums,target);
    }
    
    int bsearch(int s, int e, vector<int>& nums, int target){
        //check edge case
        //the opposit case of s<=e
        if(s>e){
            return s;
        }
        
        //check middle
        int m = (s+e)/2;
        
        if(target==nums[m]){
            return m;
        }
        
        //process current situation
        if(target<nums[m]){
            //search left, s to m-1
            return bsearch(s,m-1,nums,target);
        }
        
        //last case
        //search right, m+1 to e
        return bsearch(m+1,e,nums,target);   
    }
};

34 This question extend the original form of binary search from one branch to the two branch, so it is not conveient use the while loop style program to go through one brach of the tree each time. The basic form to considing this quesiton is as follows: The goal is to find the left end and the right end of the substr. The original two pointer approach is to set a start and end pointer at the each end of the array, then move from the middle if they does not equal with target. When they does not equal, just move, the logic is simple, but this is O(n) time complexity.

For the O(logn) case, we split the whole array into three cases at each iteration, mid element, left part of the middle (from negative infinity to mid-1), right part of the middle (from mid+1 to the positive infinity), for the general case, if the middle equals to the target, then left end and right end of the substr is at the left range and right range, then we just need to write a recursive style algorithm to do similar things. At each iteration, we update left and right when we hit the situation when v[mid] equals target. Be care of the edge case, when position of mid index is out of the range between left to right index, we return it.

class Solution {
    int spos=INT_MAX;
    int epos=INT_MIN;
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        
        //bsearch
        int s = 0;
        int e = nums.size()-1;
        bsearch(s,e,nums,target);
        
        if(spos==INT_MAX || epos==INT_MIN){
            //did not find
            return {-1,-1};
        }
        
        vector<int> ans = {spos,epos};
        return ans;
    }
    
    //binary search
    //start pos, end pos
    void bsearch(int s, int e, vector<int>& nums, int& target){
        //if the end of the tree
        int mid = (s+e)/2;
        if(mid<s || mid >e){
            return;
        }
        
        //the opertion in curren node
        if(nums[mid]==target){
            if(mid<spos) spos = mid;
            if(mid>epos) epos = mid;
        }
        //search left half in dfs manner
        bsearch(s,mid-1,nums,target);
            
        //search right half in dfs manner
        bsearch(mid+1,e,nums,target);
        
        return;
    }
};

704 The idea is similar to previous one, it is easy to come up with a binary search solution based on while loop

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int s=0;
        int e=nums.size()-1;
        //the termination condition of searching is s>e
        while(s<=e){
            int m = (s+e)/2;
            if(nums[m]==target){
                return m;
            }
            if(target<nums[m]){
                //search left
                e=m-1;
            }else{
                s=m+1;
            }
        }
        return -1;   
    }
};

981 Time Based Key-Value Store The value stored in the map should be sorted according to the timestep, which is tyical binary search use case scenarios. In some online code (huahua’s code), we can use upper_bound function to get the first element in array which is larger than dedicated value. However, we can use a binaray search based subroutine here.

33.Search in Rotated Sorted Array. This question use binary search as a subroutine to process this. We first to find the pivotal element, then search the 0 to p and p to end respectively by binary search to find the target element.
The operation to find the pivotal element is tricky, it is actually the first element in the array that is larger then num[0]. Just be careful about when to use +1 in the binary search, the edge case can be hard to debug.

One key point is that, for the binary code to find value that equals to target exactly, each binary search, we get three situations, the current element is what we find, or the dedicated element is at the left segment, or the dedicated element is at the right segment. so we use m+1 and m-1 in the next round binary search. For this case, when the value at current position is larger than num[0], it is still can be the element we want to find, so we keep it in the next round (let h = m).

class Solution {
public:
    int search(vector<int>& nums, int target) {
        //find pivotal pos p
        int l=0;
        int h=nums.size()-1;
        //p is the first one in the second segment
        while(l<h){ 
           //only need to compare with the first elem
           int m=(l+h)/2; 
           if(nums[m]>=nums[0]){
               //in the left segment
               l = m+1;
           }else{
               //in the right segment
               h = m;
           }  
        }
        //pivotal elem is 
        int p = l;
        if(target>=nums[p] && target<=nums[nums.size()-1]){
            //bsearch l to size-1
            return bsearch(nums,target,p,nums.size()-1);
        }
        //else, search 0 to p
        return bsearch(nums,target,0,p-1);
    }
    
    int bsearch(vector<int>& nums, int target, int l, int h){
        while(l<=h){
            int m = (l+h)/2;
            if(nums[m]==target){
                return m;
            }
            if(target<nums[m]){
                //search left
                h=m-1;
            }else{
                l=m+1;
            }
        }
        return -1;
    }
};

81 Search in Rotated Sorted Array II. For this one, the first step is to find out the pivotal element. Then we can know 0 to p and p+1 to size-1 in the array are sorted, respectively. And we can use the binary serach for searching the target element. Since there is repeated elements in the string, there is no simple way to use binaray search to find the targeted element (such as case [1,1,1,1,5,1,1] the mid element is still 1, we do not know if to move to left or right branch for the next iteration). We just use the linear searching to find the first position where nums[i]<nums[i-1] the nums[i] is the pivotal element.

Actually the 154 can be the first part of this question. However, it is a little bit hard to think all possibilities clearly. (The key is that, it is not always the O(logN)), we can make it O(logN) at best case and O(N) at the worst case. This is still better than O(N).

class Solution {
public:
    int findFirstDecreasePos(vector<int>& nums){
        int size = nums.size();
        for(int i=1;i<size;i++){
            if(nums[i]<nums[i-1]){
                return i;
            }
        }
        return -1;
    }
    bool search(vector<int>& nums, int target) {
        if(nums.size()==1){
            return nums[0]==target;
        }
        int p = findFirstDecreasePos(nums);
        //printf("lower bound index p %d\n",p);
        if(p==-1){
            //all elements is larger or equal to current one
            return bsearch(nums,target,0,nums.size()-1);
        }   
        if(target>=nums[p] && target<=nums[nums.size()-1]){
            //bsearch start to size-1
            return bsearch(nums,target,p,nums.size()-1);
        }
        //search 0 to p
        return bsearch(nums,target,0,p-1);
    }
    bool bsearch(vector<int>& nums, int target, int l, int h){
        int m=0;
        while(l<=h){
            m = (l+h)/2;
            if(nums[m]==target){
                return true;
            }else if(nums[m]<target){
                l=m+1;
            }else{
                //>target
                h=m-1;
            }
        }
        return false;
    }
};

153 Find Minimum in Rotated Sorted Array. This is ctually the first part of the question 33 to find the pivotal element. Since the question said the element is unique, we can use binaray search to accelarate the finding procedure. Just using nums[0] as a pivotal element and then we can continue find the pivotal element, which is the start position of the second segment and it is also the minimal element in the array. Be careful about the return value, it should be the l. Since we need to return the first element of the second segment, not the last element of the first segment.

class Solution {
public:
    int findMin(vector<int>& nums) {
        //find pivotal pos p
        int l=0;
        int h=nums.size()-1;
        int p=0;
        //p is the first one for the second segment
        //p here is the origianl start position
        //which is also index for the minimal value
        if(nums[h]>nums[0]){
            //normal order
            return nums[0];
        }
        while(l<h){ 
           //only need to compare with the first elem
          p=(h+l)/2; 
          if(nums[p]>=nums[0]){
               l = p+1;
           }else{
               h = p;
           }  
        }
        return nums[l];    
    }
};

154 Find Minimum in Rotated Sorted Array II. It is tricky but inspiring to consider all kinds of cases clearly (that is the key points to use the binary search). This answer provides a really good analysis. However, it seems that the code can be simplified based on 153, we just add an specical case to check the situation when there is repeated elements.

During each iteration, there are three cases, (1) when nums[m]==nums[r], we do not have clear thought about the minimal element’s position, it can be [1,1,1,5,1,1] or [1,5,1,1,1] so we just decrease r in a linear way. (2) when nums[m]<nums[r], the m position is at the right side of the subarray. If the m is at the left side, there is nums[m]>nums[0]>nums[n-1] (after rotating, we can guarantee there is nums[0]<nums[n-1]) which conflict with condition, so m position is at left side. (3) Similarly, when nums[m]>nums[r], the m’s position is at right side. In this case we only let r=m instead of r=m-1 since the m can be the position of minimal value exactly.

class Solution {
public:
    int findMin(vector<int>& nums) {
        int n = nums.size();
        int l = 0, r = n - 1;     
        while(l < r) {
            int m = (l+r)/2;
            if(nums[m]==nums[r]){
                //duplicated case
                r=r-1;
            }else if(nums[m]<nums[r]){
                r=m;
            }else{
                //nums[m]>nums[r]
                l=m+1;
            }
        }
        //pivotal is l
        return nums[l];
    }
};

162 Find Peak Element. We have 4 classifications for the middle one, when it is at the peak, at the bottom (just either move l or r), in the ascending part or in the decending part, then we can move l or r make it close to the large end. Be careful with the edge cases a little bit. The condition is made by comparing m with m-1 and m+1, so we need to consider the case when m is at 0 or n-1 position. 852 is a similar version to this one, we do not list detailed solution of 852, they use similar idea to do the classification.

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int l=0;
        int r=nums.size()-1;
        int m=0;
        //edge cases
        if(r==0){
            //one elements
            return 0;
        }
        if(r==1){
            return nums[l]>nums[r]?0:1;
        }
        //moving to the direction 
        //where there is larger element
        while(l<=r && l>=0 && r<=(nums.size()-1)){
            m = (l+r)/2;
            //edge cases
            //we need to consider it since the 
            //condition is determined by m m-1 and m+1
            if(m==0){
                return nums[m]>nums[m+1]?m:m+1;
            }
            if(m==(nums.size()-1)){
                return nums[m]>nums[m-1]?m:m-1;
            }
            if(nums[m]>nums[m-1] && nums[m]>nums[m+1]){
                //the peak case
                return m;
            }else if (nums[m]>nums[m-1] && nums[m]<=nums[m+1]){
                //ascending case, move to right
                l=m+1;
            }else if (nums[m]<=nums[m-1] && nums[m]>nums[m+1]){
                //descending case, move to left
                r=m-1;
            }else if (nums[m]<=nums[m-1] && nums[m]<=nums[m+1]){
                //either moving direaction is ok
                l=m+1;
            }
        }
        return m;
    }
};

852 Peak Index in a Mountain Array. Be careful about this case, the element can be at the minimal position. For other cases, they are similar to the previous one, increasing, decreasing, top of the mountain, at the end of arrays. etc.

class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        // assuming the mountain exist
        // and elements is larger than 3
        int l=0;
        int r=arr.size()-1;
        int m=0;
        while(l<=r){
            m = (l+r)/2;
            //when there are two elements
            //and m equals to either l or r
            if(m==l || m==r){
                //mountain point is at the start or end position of array
                return arr[l]>arr[r]?l:r;
            }   
            //when there are more than 2 elements in the range
            if(arr[m]>arr[m-1] && arr[m]>arr[m+1]){
                //exact mountain point
                return m;
            }else if (arr[m]>arr[m-1] && arr[m]<=arr[m+1]){
                //increasing order
                l=m+1;
            }else if (arr[m]<=arr[m-1] && arr[m]>arr[m+1]){
                //decreasing order
                r=m-1;
            }else if (arr[m]<=arr[m-1] && arr[m]<=arr[m+1]){
                //minimal point
                l=m+1;
            }
        }
        return m;
    }
};

69 Sqrt(x) This is the first type of close to target question. The condition of this type question is different with previous one to find exact target. If we use previous condition such as l<r, it is hard to tell which one is more close to the target point. For example, when we compute sart(8) in this case, if there is l<r in the condition, the final step of l and r is both 3. If we choose to use l<=r, the position of l and r are swithced around the targed elements, so we can find the closer one by return min(l,r), or just return r. Another issue that we need to pay attention is the range of the number (we use long long int for this question), and the edge case, such as when there is 0 and 1 for this question.

class Solution {
public:
    int mySqrt(int x) {
        int l=0;
        int r=x;
        long long int m=0;
        if(x==0 || x==1){
            return x;
        }
        while(l<=r){
            m=(l+r)/2;
            long long int m2 = m*m;
            if(m2==x){
                return m;
            }else if(m2<x){
                l=m+1;
            }else{
                r=m-1;
            }
        }
        return r;
    }
};

74 Search a 2D Matrix. This is a simple extension from 1d to 2d, for the 2d case, we need to use two pointer, one is to index the middle position of row, another is to index the middle position of column. Be careful about the pointer case when we move the row index, we need to reset the left and right column index back to 0 and n-1 each time.

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int row = matrix.size();
        int col = matrix[0].size();
        int row_l=0;
        int row_r=row-1;
        int col_l=0;
        int col_r=col-1;
        while(row_l<=row_r && col_l<=col_r){
            //searching
            int row_m=(row_l+row_r)/2;
            int col_m=(col_l+col_r)/2;
            if(matrix[row_m][col_m]==target){
                return true;
            }else if(matrix[row_m][col_m]>target){
                //can be same row or different row
                if(matrix[row_m][0]<=target){
                    //same row, move col
                    col_r=col_m-1;
                }else{
                    //different rows
                    row_r=row_m-1;
                    //reset col index
                    col_l=0;
                    col_r=col-1;
                }
            }else{
                //m[row_m][col_m]<target
                if(matrix[row_m][col-1]>=target){
                    //same row, move col
                    col_l=col_m+1;
                }else{
                    //different rows
                    row_l=row_m+1;
                    //reset col index
                    col_l=0;
                    col_r=col-1;
                }
            }
        }
        return false; 
    }
};

875 Koko Eating Bananas. This is also the one to find the value close to the target. The fancy part that in each iteration, when we decide the condition, it is not straightforward comparison between the middle value with the target value, we need to use a function such as canFinish here to decide it. This is a good exmaple to use the binary search to solve problem with interesting background.

class Solution {
public:
    bool canFinish(vector<int>& piles, const int h, const int k){
        int size = piles.size();
        int takeHours=0;
        for(int i=0;i<size;i++){
            int currNum=piles[i];
            int currTakeHour=currNum%k==0?currNum/k:(currNum/k)+1;
            takeHours=takeHours+currTakeHour;
            if(takeHours>h){
                return false;
            }
        }
        return true;
    }
    int minEatingSpeed(vector<int>& piles, int h) {
        //range of the k
        auto result = std::max_element(piles.begin(), piles.end());
        int kl=1;
        int kr=*result;

        while(kl<=kr){
            int km=(kl+kr)/2;
            if(canFinish(piles, h, km)){
                kr=km-1;
            }else{
                kl=km+1;
            }
        }
        return kl;
    }
};

1011 TThis is a little bit similar to previous one (875) The interesting part is that although we are given an array, but we actually not use binary search to search that array. That array is just an tool to help us to determine if the current answer is good enough. The good strategy so solve this type of problem is to draw a line that labesl the relatipnship between two variables, we basicaly move a 1d case binary search to a 2d case binary search.

What we need to compare is the number of days we can complete the work. This number has a positive relationship with the size of package. What we can control is the size of package, and what we need to compare is the size of days. We chage package size and find a completion days that close to the one provided by question.

Understanding “no less than” is important, it means closest value of the bag size from right side of the weight axis. Try to draw a 2-d plot the y axis is the days and the x axis is the weight of the package, the line shows an decreasing trend.

Be careful about the start and end position of the weight in this question, the right element should be the sum of all weights.

Another small trick we can learn from this question’s coding is the programming for the for loop. The ensential pattern of the loop is 1 do some computation, 2 update some metadata if we consider it logically. such as pattern in this: --|--|--| however, in practial programming, we may use some condition to detect if we need to move the element to the next iteration. --*|--*|... where * represent the condition checking to move to next element. We might forget to update the metadata when exit the loop. The good practice might be to make each for loop indepedent. If we need to introduce some depedency anyway (we can use dummy element or maybe write the sequence of for loop, such as pattern we shoned above before programming), don’t forget to update metadata when exit the for loop, for the last elements, there might some specical case.

class Solution {
public:
    //if the package with w can complete all tasks within d days
    int canFinish(int targetd, int w, const vector<int>& weights){
        int cd=0;
        int cw=0;
        for(int i=0;i<weights.size();i++){
            if(w<weights[i]){
                //the bag size too small
                //there is no way to put it into the bag
                return false;
            }
            if(cw+weights[i]<=w){
                //cw has enough space to load weights[i]
                cw+=weights[i];
            }else{
                //cw do not have enough space
                //update states for the last time
                cd+=1;
                //return earlier
                if(cd>targetd){
                    return false;
                }
                //reset cw and put current one into the bag
                cw=weights[i];
            }
        }
        //for the last element, we did not +1
        cd=cd+1;
        return cd<=targetd;
    }
    int shipWithinDays(vector<int>& weights, int days) {
        //assuming days < weights length
        //range of w, its size can not be smaller than the min element
        int wl=*std::min_element(weights.begin(), weights.end());
        //the largest one can be sum of all weight
        int wr = std::accumulate(weights.begin(), weights.end(), 0);
        while(wl<=wr){
            int wm=(wl+wr)/2;
            if(canFinish(days,wm,weights)){
                //try to decrease weight
                //if we can finish the task
                wr=wm-1;
            }else{
                wl=wm+1;
            }
        }
        return wl;
    }
};

4 This is a hard one, just jump this temporarily. The key difficulty is figure out why the midean elements are one of these four elements in two sorted array.
Maybe learn from this video:
https://leetcode.com/problems/median-of-two-sorted-arrays/solutions/4397580/99-87-beginner-friendly-video-optimal-solution-explained/

378

Understand the question: kth smallest element, k starts from 1. It means that for all the element before position of current value v, there are k-1 elements that have value less or equal to the v (Be careful, we include the one with value that equals to v here). This is a function of the original given value, which can be a second variable.

The most tricky part in this question is figure out what is the first variable (searching space that can be used in binary search). It start from the smallest element in the matrix and the end with the last element in the matrix. The matrix is just a tool used for derive the value of the second variable. Do not mix this type of problem with 74, they are differet, for 74, the searching space is just that matrix, and the first element in each row is larger than the last one in the previous row. But the matrix in current one is different, there is no guarantee about the relationship between the last element in previous row and first element in the current row.

Another tricky part is that the property of the matrix. It is ascending in row and colum, it means that m[i][j]<m[i][j+1] and m[i][j]<m[i+1][j]. But is does not mean that the last element in previous row less or equals to the first element in the current row.

The logic to find the number of element that is less or equal to the target is not quite straightforward to understand. Assuming 0,0 position is at the top left corner of the matrix. We look at first column, find how many element less or equal to the target one. Then goes to the second column, so on so forth. This is one version of code to go through the matrix to find how many elements are less or equal than dedicated one. We use a for loop plus a while loop. Altough it is simple to understand, it takes me a little while to think it in a clear way.

int countLess(vector<vector<int>>& m, int v){
    //count how many element in the matrix is less or equals to v
    int n=m.size();
    int i=0;
    int j=0;
    int c=0;
    for(j=0;j<=n-1;j++){
        while(i<=n-1 && m[i][j]<=v){
            c=c+1;
            i++;
        }
        //set i's position back to the first row
        //start checking next column
        i=0;
    }
    return c;
}

Using this kernel with the typical framework of binary search, we can find the element that have kth smaller element in the matrix. Be careful about the repeated value.

The last step is to map the middle element back to the element in the matrix. The middle element, L and R value might not exist in the matrix. So we need to find element in the matrix that is cloeset to what we find. There are two cases, when the L <= R, it means we need to find first element in the matrix that is equal or larger than m. When the L and R are switched, it means there are a lot of same repeated elements:

[[1,1,3,8,13],[4,4,4,8,18],[9,14,18,19,20],[14,19,23,25,25],[18,21,26,28,29]]
k=13

For this case, when m is 17, the ck value is 12, when m is 18 the ck value is 15, but the target is 13. So the L and R are switched at last, the element we need to find within the upper bounud that equals to the L’s value (L and R are switched). This is the compete solution, we use similar strategy to check the matrix and find the element that using L value as its upper bounud.

class Solution {
public:
    //the idea is to searching all 2d space and see how many element is less than
    //targeted one
    int countLess(vector<vector<int>>& m, int v){
        //count how many element in the matrix is less or equals to v
        int n=m.size();
        int i=0;
        int j=0;
        int c=0;
        for(j=0;j<=n-1;j++){
            while(i<=n-1 && m[i][j]<=v){
                c=c+1;
                i++;
            }
            //set i's position back to the first row
            //start checking next column
            i=0;
        }
        return c;
    }
    //using t as the upper bounud
    //find element in the matrix m that close to t as much as possible
    int lessClose(vector<vector<int>>& m, int t){
        int n=m.size();
        int i=0;
        int j=0;
        //init value of v is the smallest element in matrix
        int v=m[0][0];
        for(j=0;j<=n-1;j++){
            while(i<=n-1 && m[i][j]<=t){
                //store the largest one
                v=max(v,m[i][j]);
                i++;
            }
            //find the one that is larger than m, break
            //rest i to zero
            i=0;
            if(v==t){
                //we have found the t value 
                break;
            }
        }
        return v;
    }

    int kthSmallest(vector<vector<int>>& matrix, int k) {
        int n=matrix.size();
        int L=matrix[0][0];
        int R=matrix[n-1][n-1];
        int m;
        while(L<=R){
            m = (L+R)/2;
            int ck = countLess(matrix, m);
            //printf("debug L %d R %d m %d ck %d\n",L,R,m,ck);
            if(ck==k){
                //keep the m
                break;
            }else if(ck<k){
                L=m+1;
            }
            else{
                //ck>k
                R=m-1;
            }
        }
        if(L<=R){
            //go through matrix find value close to m
            return lessClose(matrix,m);
        }
        //L and R are switched, using L as the upper bounud
        return lessClose(matrix,L);
    }
};

668

719

786