General

start < end

• [start, end), end 為開區間

• while退出條件為 target < start = end

public int binarySearch(int[] arr, int target){
    int start = 0; end = arr.length;  // [start, end)
    // target <= start = right
    while(start < end){
        int mid = start + (end - start)/2;
        if(mid > target) end = mid;
        else if (mid < target) start = mid+1;
        else return mid;
    }

    // 返回target 前一個 index
    return start;
}

start + 1 < end

• while 直到 [[start][end]]相鄰退出,

• if duplicate, 會在頭兩個的位置

• find last element of target, if (nums[mid] == target) start = mid

public int findPosition(int[] nums, int target) {
    if (nums == null || nums.length == 0){
        return -1;
    }

    int start = 0, end = nums.length - 1;
    while (start + 1 < end){
        int mid = start + (end - start) / 2;
        if (nums[mid] == target){
            end = mid;
        }else if (nums[mid] < target){
            start = mid;
        }else{
            end = mid;
        }
    }

    if (num[start] == target){
        return start;
    }
    if (num[end] == target){
        return end;
    }
    return -1;
}

34 Find First and Last Position of Element in Sorted Array

Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.

Your algorithm's runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

public int[] searchRange(int[] nums, int target) {
    int[] ans = new int[2];
    if(nums == null || nums.length == 0) return new int[]{-1, -1}; 
    int start = 0, end = nums.length-1;
    while(start+1 < end){
        int mid = start + (end-start)/2;
        if(nums[mid] == target) end = mid;
        else if(nums[mid] < target) start = mid;
        else end = mid;
    }

    if(nums[start] == target) ans[0] = start;
    else if(nums[end] == target) ans[0] = end;
    else ans[0] = -1;

    start = 0;
    end = nums.length-1;
    while(start+1 < end){
        int mid = start + (end-start)/2;
        if(nums[mid] == target) start = mid;
        else if(nums[mid] < target) start = mid;
        else end = mid;
    }

    if(nums[end] == target) ans[1] = end;
    else if(nums[start] == target) ans[1] = start;
    else ans[1] = -1;

    return ans;
}

74 find element in a 2-D array

[[1,2,3] [4,5,6] [7,8,9]]

end = row * column - 1
mid = (start + end) / 2
num = nums[mid/column][mid%column]

240 find element in a 2-D array ll

Find a occurrence of given number in a 2-D array

[[1,2,3 [2,3,4] [3,4,5]]

• Search from bottom left to top right

• each row is sorted, start new search y index from row + 1

public int searchMatrix(int[][] matrix, int target) {
    int m = matrix.length, n = matrix[0].length;
    int x = m, y = 0;
    int count = 0;
    // search from bottom left to top right
    while (x >= 0 && y <= n){
        if (matrix[x][y] < target){
            y++;
        }else if(matrix[x][y] > target){
            x--;
        }else{
            count++;
            y++;
            x--;
        }
    }
    return count;

702 Search in a big sorted array with unknown size

Given an integer array sorted in ascending order, write a function to search target in nums. If target exists, then return its index, otherwise return -1. However, the array size is unknown to you. You may only access the array using an ArrayReader interface, where ArrayReader.get(k) returns the element of the array at index k (0-indexed).

public int search(ArrayReader reader, int target) {
    int index = 1;
    while(reader.get(index-1) < target) index *=2;

    int start = index/2, end = index-1;
    while(start+1 < end){
        int mid = start + (end-start)/2;
        if(reader.get(mid) <= target) start = mid;
        else end = mid;
    }

    if(reader.get(start) == target) return start;
    if(reader.get(end) == target) return end;
    return -1;
}

Search the insert position

• One more scenario to define [1,2,3], target = 4

• Use target to define return position

public int searchInsert(int[] A, int target) {
    // find first less or equal then target
    if (A == null || A.length == 0){
        return 0;
    }

    int start = 0, end = A.length -1;

    while(start+1 < end){
        int mid = start + (end-start)/2;
        if (A[mid] == target){
            start = mid;
        }else if (A[mid] < target){
            start = mid;
        }else{
            end = mid;
        }
    }

    // use target to define return position
    if (target <= A[start]){
        return start;
    }else if (target <= A[end]){
        return end;
    }else{
        return end + 1;
    }
}

Count of smaller number

• Sort A first

• Not include the target number => similar to "insertion position"

public List<Integer> countOfSmallerNumber(int[] A, int[] queries) {
    List<Integer> result = new ArrayList<>();

    if (queries == null || queries.length == 0){
        return result;
    }

    int lenA = A == null ? 0 : A.length;

    Arrays.sort(A);
    for (int i =0; i < queries.length; i++){
        if(lenA == 0){
            result.add(0);
        }else{
            result.add(binarySearch(A, queries[i])); 
        }
    }
    return result;
}


private int binarySearch(int[] A, int target){
    int start = 0, end = A.length -1;
    while(start + 1 < end){
        int mid = start + (end-start)/2;
        if (A[mid] == target){
            end = mid;
        }else if (A[mid] < target){
            start = mid;
        }else{
            end = mid;
        }
    }

    // not include target
    if (target <= A[start]){
        return start;
    }else if (target <= A[end]){
        return end;
    }else{
        return end + 1;
    }
}

658. Find K closest Elements

Given a sorted array, two integers k and x, find the k closest elements to x in the array.

• A[i] to A[i+k-1]

• Binary search, 利用 x 與兩邊的距離

• x = 3, k =2 [1,1,2,2,2,2,2,3,3], 需特別處理 兩邊到x距離相等的情況

def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
    l, r = 0, len(arr)-k
    while l < r:
        mid = (l+r)//2
        if arr[mid] == arr[mid+k]:
            if x > arr[mid]: l = mid+1
            else: r = mid

        elif abs(arr[mid] - x) > abs(arr[mid+k] - x):
            l = mid+1
        else:
            r = mid
    return arr[l: r+k]