1、二分查找法

二分查找法（Java 实现）

template<typename T>
int binarySearch1(T arr[], int n, T target) {
    // 在 [l ... r] 的范围里寻找 target
    int l = 0;
    int r = n - 1;
    int mid;

    // 当 l == r 时, 区间 [l ... r] 依然是有效的
    while (l <= r) {
        mid = l + (r - l) / 2;
        if (arr[mid] == target) return mid;
        if (arr[mid] < target) l = mid + 1;
        else r = mid - 1;
    }

    return -1;
}

template<typename T>
int binarySearch2(T arr[], int n, T target) {
    // 在 [l ... r) 的范围里寻找 target
    int l = 0;
    int r = n;
    int mid;

    // 当 l < r 时, 区间 [l ... r) 就是有效的
    while (l < r) {
        mid = l + (r - l) / 2;
        if (arr[mid] == target) return mid;
        if (arr[mid] < target) l = mid + 1;
        else r = mid;
    }

    return -1;
}

2、移动零

283 - 移动零
27 - 移除元素
26 - 删除有序数组中的重复项
80 - 删除有序数组中的重复项 II

#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    /**
     * 时间复杂度: O(N)
     * 空间复杂度: O(N)
     */
    void moveZeroes1(vector<int> &nums) {
        vector<int> temp;

        for (const auto &item: nums) {
            if (item != 0) temp.push_back(item);
        }

        for (int i = 0; i < temp.size(); ++i) {
            nums[i] = temp[i];
        }

        for (int i = temp.size(); i < nums.size(); ++i) {
            nums[i] = 0;
        }
    }

    /**
     * 时间复杂度: O(N)
     * 空间复杂度: O(1)
     */
    void moveZeroes2(vector<int> &nums) {
        // [0 ... p) 存放的都是非 0 元素
        int p = 0;

        for (const auto &item: nums) {
            if (item != 0) nums[p++] = item;
        }

        for (int i = p; i < nums.size(); ++i) nums[i] = 0;
    }

    /**
     * 时间复杂度: O(N)
     * 空间复杂度: O(1)
     */
    void moveZeroes3(vector<int>& nums) {
        // [0 ... p) 存放的都是非 0 元素
        int p = 0;
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] != 0) {
                if (p != i) swap(nums[p++], nums[i]);
                else p++;
            }
        }
    }
};

int main() {
    int arr[] = {0, 1, 0, 3, 12};
    vector<int> vec(arr, arr + sizeof(arr) / sizeof(int));

    Solution().moveZeroes(vec);

    for (int i : vec) cout << i << " ";
    cout << endl;

    return 0;
}

/**
 * 时间复杂度: O(N)
 * 空间复杂度: O(N)
 */
public static void moveZeroes1(int[] nums) {
    int[] temp = new int[nums.length];
    int index = 0;
    for (int num : nums) {
        if (num != 0) temp[index++] = num;
    }
    System.arraycopy(temp, 0, nums, 0, temp.length);
}

/**
 * 时间复杂度: O(N)
 * 空间复杂度: O(1)
 */
public static void moveZeroes2(int[] nums) {
    // [0 ... p) 存放的都是非 0 元素
    int p = 0;
    for (int num : nums) {
        if (num != 0) nums[p++] = num;
    }
    Arrays.fill(nums, p, nums.length, 0);
}

/**
 * 时间复杂度: O(N)
 * 空间复杂度: O(1)
 */
public static void moveZeroes3(int[] nums) {
    // [0 ... p) 存放的都是非 0 元素
    int p = 0;
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] != 0) {
            if (p != i) swap(nums, p++, i);
            else p++;
        }
    }
}

private static void swap(int[] nums, int a, int b) {
    int k = nums[a];
    nums[a] = nums[b];
    nums[b] = k;
}