Binary Search

Binary Search

Can be done on

• index
• range Eg: https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/discuss/301357/Java-0ms-(added-Python-and-C%2B%2B)%3A-Easy-to-understand-solutions-using-Heap-and-Binary-Search

Resources

https://www.topcoder.com/community/competitive-programming/tutorials/binary-search/ https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/discuss/85225/Quick-Select-and-Binary-Search-(detailed-notes)

Paterns

If you want to store the result in high , make sure initial value of high is end+1

int low = start + 1;
        int high = end + 1;
        int mid, cand;
        
        while (low < high) {
            mid = low + (high - low)/2;
            if (preorder[mid] > preorder[start]) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }
        root.left = util(preorder, start+1, high - 1);
        root.right = util(preorder, high, end);

Submission link

If you want to store the result in low, make sure high = end and you change high = mid -1

int low = start + 1;
        int high = end;
        int mid, cand;
        
        while (low <= high) {
            mid = low + (high - low)/2;
            if (preorder[mid] > preorder[start]) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        root.left = util(preorder, start+1, low - 1);
        root.right = util(preorder, low, end);

Submission link

If you are using low <= high make sure you are changing high to mid-1 else it will go into infinite loop. Else use low < high