Binary Search

1. Special cases when array is null or length is 0;
2. Loop condition (start+1 < end), stops when start is next to end;
3. Assign middle: middle = start + (end - start)/2, avoid overflow;
4. Compare cases: ==, <, >;

Find Minimum in Rotated Sorted Array II

Analysis: This problem allows duplicates. So special scenario could happen that mid, start and end all have same value.

What we gonna do is to test whether num[start]==num[end], if so, move start pointer right till they have different values.

Worst case would take O(n)

Notice: Need to cover the situation that resultant array is unrotated.

public static int findMinBS(int[] num) {
        if (num == null || num.length == 0)
            return Integer.MAX_VALUE;


        int start = 0;
        int end = num.length - 1;
        int mid;
        while (end - start > 1) {
            while (num[start] == num[end] && start != end) {
                start++;
            }

            // When the array is not rotated
            if (num[start] <= num[end])
                return num[start];

            mid = start + (end - start)/2;
            if (num[mid] >= num[start]) {
                start = mid;
            } else {
                end = mid;
            }
        }

        return Math.min(num[start], num[end]);
    }

Find the Duplicate Number

Analysis: In this problem, we regard the range [1,n] as our search array. Make mid = start + (end - start)/2 and count number of elements not greater than mid. If count > mid, then the duplicate number is smaller than mid; else, the duplicate number is larger than mid.

public int findDuplicate(int[] nums) {

        if (nums == null || nums.length == 0)
            return -1;

        int start = 1;
        int end = nums.length - 1;
        int mid;
        while (start <= end) {
            mid = start + (end - start)/2;

            int count = 0;
            for (int i=0; i < nums.length; i++) {
                if (nums[i] <= mid)
                    count++;
            }

            if (count > mid) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        return start;
    }

Divide Two Integers

Analysis: We can use bit operation to make divisor multiply by 2 until it's right less than dividend. Then take the difference and keep left shift. Till the difference is less than divisor.

Notice: The special cases here are really tricky. Need to consider when divisor==0, dividend==0 and dividend==Integer.MIN_VALUE&&divisor==-1. Need to notice when we get absolute value of dividend and divisor we need to use long cause one of them could be Integer.MIN_VALUE.

public int divide(int dividend, int divisor) {
        if (divisor == 0) {
            return dividend > 0 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
        }
        if (dividend == 0) {
            return 0;
        }
        if (dividend == Integer.MIN_VALUE && divisor == -1) {
            return Integer.MAX_VALUE;
        }

        boolean sign = ((dividend > 0) && (divisor > 0)) || ((dividend < 0) && (divisor < 0));
        int result = 0;

        long a = Math.abs((long)dividend);
        long b = Math.abs((long)divisor);

        while (a >= b) {
            int shift = 0;

            while (a >= (b << shift)) {
                ++shift;
            }
            result += 1 << (shift - 1);
            a -= b << (shift - 1);
        }
        return sign ? result : (-result);
    }