求和问题總结

题目列表

• 問题描述

總結

1. Binary Search Templates (4 key pointers)
2. Rotated Sorted Array
   a. find minimum
   b. find target
   c. why o(n) with duplicates?
3. Find Median in Two Sorted Array
   find kth
4. Reverse in 3 steps

注意事项

• 可能有重覆项，要確認是在Any/First/Last position of target in

關係聯想：

1. Sorted Array: 左右拆分
2. O(logn)

3. Tricky way:

   1. Find the Duplicate Number

Templates
public int binarySearch(int[] A, int target){
    int start = 0;
    int end = A.size() - 1;
    while( start + 1 < end){
        int mid = start + (end - start) / 2;  //考慮到溢出
        if(A[mid] == target){
            end = mid;
        }else if(A[mid] > target){
            end = mid;
        }else{
            start = mid;
        }
    }
    if(A[start] == target){
        return start;
    }
    if(A[end] == target){
        return start;
    }

    return -1;
}