Programmer: Lifelong Learning: Binary Search (Tree) + Bisection

Binary search
- Prefer [], start=0, end=len-1
- int mid = left + (right - left) / 2;
- if low

public int searchRightIndex(int[] nums, int left, int right, int target) {
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] > target) right = mid - 1;
else left = mid + 1;
}
return right;
}
public int searchLeftIndex(int[] nums, int left, int right, int target) {
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] < target) left = mid + 1;
else right = mid - 1;
}
return left;
}

LeetCode 35 - Search Insert Position
LeetCode 34 - Search for a Range
find the starting and ending position of a given target value.
start = Solution.firstGreaterEqual(A, target);
end = firstGreaterEqual(A, target + 1) - 1;

LeetCode 278 - First Bad Version
http://www.cnblogs.com/anne-vista/p/4848945.html

LeetCode 374 - Guess Number Higher or Lower
https://leetcode.com/articles/guess-number-higher-or-lower/

X. Search in rotated sort array
LeetCode 153 - Find the minimum element in a sorted and rotated array

LeetCode 33 - Searching an Element in a Rotated Sorted Array

    public int search(int[] nums, int target) {
        int start = 0;
        int end = nums.length - 1;
        while (start <= end){
            int mid = (start + end) / 2;
            if (nums[mid] == target)
                return mid;
        
            if (nums[start] <= nums[mid]){// can be just < as no duplicate
                 if (target < nums[mid] && target >= nums[start]) 
                    end = mid - 1;
                 else
                    start = mid + 1;
            } 
        
            if (nums[mid] <= nums[end]){//<
                if (target > nums[mid] && target <= nums[end])
                    start = mid + 1;
                 else
                    end = mid - 1;
            }
        }
        return -1;
    }

LeetCode 81 - Search in Rotated Sorted Array II

LeetCode 153 - Find the minimum element in a sorted and rotated array

LeetCode 154 - Find Minimum in Rotated Sorted Array II

LeetCode - Sqrt(x)

Bisection
- Suppose we know the answer, it's easier to determine whether the answer is true/possible
- isPossible(**, int curValue)

LeetCode 287 - Find the Duplicate Number
Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive),
- Constant space, don't modify the array
- Bisection (1, nums.length-1)
- 32(n)

public int findDuplicate(int[] nums) {
    int n = nums.length-1, res = 0;
    for (int p = 0; p < 32; ++ p) {
        int bit = (1 << p), a = 0, b = 0;
        for (int i = 0; i <= n; ++ i) {
            if (i > 0 && (i & bit) > 0) ++a;
            if ((nums[i] & bit) > 0) ++b;
        }
        if (b > a) res += bit;
    }
    return res;
}

- O(n) find cycle in LinkedList

LeetCode 644 - Maximum Average Subarray II

find the contiguous subarray whose length is greater than or equal to k that has the maximum average value.

        for (int n: nums) {
            max_val = Math.max(max_val, n);
            min_val = Math.min(min_val, n);
        }
        double prev_mid = max_val, error = Integer.MAX_VALUE;
        while (error > 0.00001) {
            double mid = (max_val + min_val) * 0.5;
            if (check(nums, mid, k))
                min_val = mid;
            else
                max_val = mid;
            error = Math.abs(prev_mid - mid);
            prev_mid = mid;
        }

LeetCode 441 - Arranging Coins

You have a total of n coins that you want to form in a staircase shape, where every k-th row must have exactly k coins.

Given n, find the total number of full staircase rows that can be formed.

LeetCode 410 - Split Array Largest Sum

you can split the array into m non-empty continuous subarrays. Write an algorithm to minimize the largest sum among these m subarrays.

- Bisection

- TODO DP

LintCode - Copy Books

Return the number of smallest minutes need to copy all the books.

- DP

- Bisection O(nlg(sum/k)), (max, total)

Find minimum time to finish all jobs with given constraints

Facebook Hacker Cup 2012: Billboards Solution

- sizeIsDoable (1, Math.min(height, width))

            while (minSize <= maxSize) {
                // The font size that will be attempted
                int currentTargetSize = (minSize + maxSize) / 2;

                // See if the given font size fits
                if (sizeIsDoable(currentTargetSize, width, height, message)) {
                    // It fits, save as largest so far and try even larger
                    minSize = currentTargetSize + 1;
                    bestSize = currentTargetSize;
                } else {
                    // Doesn't fit, try smaller sizes
                    maxSize = currentTargetSize - 1;
                }
            }

Compute the integer/real square root

LeetCode 367 - Valid Perfect Square
- O(nlogn) Bisection (1, num/2)

Codeforces Round #318 - Bear and Elections

POJ 3104 -- Drying
Poj 3258 - River Hopscotch
POJ 3273 -- Monthly Expense
POJ 3122 - Pie

X. Binary Search tree/TreeMap/TreeSet
- [lower, upper bound]
- In order traversal, prev node
- Binary search tree: TreeSet, window size k
- Use TreeSet or TreeMap directly
- Or can't when need store extra info in node such as sameCount, leftCount

LeetCode 530 - Minimum Absolute Difference in BST
- In order traversal, prevNode
- [lower, upper bound]

LeetCode - 220 Contains Duplicate III
find out whether there are two distinct indices i and j in the array such that the absolute difference between nums[i] and nums[j] is at most t and the absolute difference between i and j is at most k.
- Bucket sort
- Binary search tree: TreeSet, window size k O(nlogk)

LeetCode 352 - Data Stream as Disjoint Intervals
- TreeMap intervals to merge interval based on start
- TreeSet

LeetCode 436 - Find Right Interval
- Use TreeMap to store intervals
- Use TreeMap> to handle duplicate start
- Sort Intervals based on start + binary search

LeetCode 493 - Reverse Pairs
we call (i, j) an important reverse pair if i < j and nums[i] > 2*nums[j].
- Build the Binary Search Tree from right to left
- Merge Sort

LeetCode 414 - Third Maximum Number
- Use PriorityQueue with HashSet to check duplicate
https://discuss.leetcode.com/topic/63086/java-priorityqueue-o-n-o-1
- TreeSet (not PQ as need call contains)
set.add(num);
if(set.size() > 3) {set.remove(set.first());}
- Maitain state: first, second, third

Binary Search (Tree) + Bisection - Algorithm

Labels