一、二分查找

template<typename T>
int bin_search(const T data[], int left, int right, T target) {
    int mid;
    while (left <= right) {
        mid = (left + right) / 2;
        if (data[mid] > target) {
            right = mid - 1;
        } else if (data[mid] < target) {
            left = mid + 1;
        } else {
            return mid;
        }
    }
    return -1;
}

二、查找最后一个小于n的值

// 查找第一个大于目标的元素
template<typename T>
int bin_search_first_greater(const T data[], int left, int right, T target) {
    int mid;
    while (left <= right) {
        mid = (left + right) / 2;
        if (data[mid] > target) {
            if (mid == left || data[mid - 1] < target)
                return mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return -1;
}

三、查找第一个大于n的值

template<typename T>
int bin_search_last_less(const T *data, int left, int right, T target) {
    int mid;
    while (left <= right) {
        mid = (left + right) / 2;
        if (data[mid] < target) {
            if (mid == right || data[mid + 1] > target)
                return mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

四、查找第一个等于n的值

template<typename T>
int bin_search_first_equal(const T *data, int left, int right, T target) {
    int mid;
    while (left <= right) {
        mid = (left + right) / 2;
        if (data[mid] < target) {
            left = mid + 1;
        } else if (data[mid] > target) {
            right = mid - 1;
        } else {
            if (mid == left || data[mid - 1] < target)
                return mid;
            right = mid - 1;
        }
    }
    return -1;
}

五、查找最后一个等于n的值

template<typename T>
int bin_search_last_equal(const T *data, int left, int right, T target) {
    int mid;
    while (left <= right) {
        mid = (left + right) / 2;
        if (data[mid] < target) {
            left = mid + 1;
        } else if (data[mid] > target) {
            right = mid - 1;
        } else {
            if (mid == right || data[mid + 1] > target)
                return mid;
            left = mid + 1;
        }
    }
    return -1;
}

六、单元测试

6.1 TestFixtures

class bin_search_test : public ::testing::Test {
protected:
    void SetUp() override {
        //                              0    1   2  3  4  5  6  7   8    9
        arr1 = new int[test_ele_count]{-23, -5, -2, 3, 8, 8, 9, 11, 54, 100};
        arr2 = new int[test_ele_count]{-1, 1, 3, 5, 5, 5, 6, 6, 6, 6};
    }

    void TearDown() override {
        delete arr1;
        delete arr2;
    }

    int *arr1;
    int *arr2;
};

6.2 测试案例

// 测试案例：二分搜索
TEST_F(bin_search_test, bin_search) {
    EXPECT_EQ(bin_search(arr1, 0, test_ele_count - 1, 9), 6);
    EXPECT_EQ(bin_search(arr1, 0, test_ele_count - 1, 54), 8);
    EXPECT_EQ(bin_search(arr1, 0, test_ele_count - 1, -23), 0);
    EXPECT_EQ(bin_search(arr1, 0, test_ele_count - 1, 100), 9);
    EXPECT_EQ(bin_search(arr1, 0, test_ele_count - 1, -1), -1);
    EXPECT_EQ(bin_search(arr1, 0, test_ele_count - 1, -3), -1);
    EXPECT_EQ(bin_search(arr1, 0, test_ele_count - 1, 7), -1);
    EXPECT_EQ(bin_search(arr1, 0, test_ele_count - 1, 60), -1);
}

// 测试案例：第一个大于目标的值
TEST_F(bin_search_test, bin_search_first_greater) {
    EXPECT_EQ(bin_search_first_greater(arr1, 0, test_ele_count - 1, 0), 3);
    EXPECT_EQ(bin_search_first_greater(arr1, 0, test_ele_count - 1, -5), 2);
    EXPECT_EQ(bin_search_first_greater(arr1, 0, test_ele_count - 1, 100), -1);
    EXPECT_EQ(bin_search_first_greater(arr1, 0, test_ele_count - 1, -24), 0);
    EXPECT_EQ(bin_search_first_greater(arr1, 0, test_ele_count - 1, 15), 8);
}

// 测试案例：最后一个小于目标
TEST_F(bin_search_test, bin_search_last_less) {
    EXPECT_EQ(bin_search_last_less(arr1, 0, test_ele_count - 1, 20), 7);
    EXPECT_EQ(bin_search_last_less(arr1, 0, test_ele_count - 1, 90), 8);
    EXPECT_EQ(bin_search_last_less(arr1, 0, test_ele_count - 1, -1), 2);
    EXPECT_EQ(bin_search_last_less(arr1, 0, test_ele_count - 1, -40), -1);
}

// 测试案例：第一个等于目标
TEST_F(bin_search_test, bin_search_first_equal) {
    EXPECT_EQ(bin_search_first_equal(arr2, 0, test_ele_count - 1, 5), 3);
    EXPECT_EQ(bin_search_first_equal(arr2, 0, test_ele_count - 1, 6), 6);
    EXPECT_EQ(bin_search_first_equal(arr2, 0, test_ele_count - 1, 1), 1);
    EXPECT_EQ(bin_search_first_equal(arr2, 0, test_ele_count - 1, 12), -1);
}

// 测试案例：最后一个等于目标
TEST_F(bin_search_test, bin_search_last_equal) {
    EXPECT_EQ(bin_search_last_equal(arr2, 0, test_ele_count - 1, 5), 5);
    EXPECT_EQ(bin_search_last_equal(arr2, 0, test_ele_count - 1, 6), 9);
    EXPECT_EQ(bin_search_first_equal(arr2, 0, test_ele_count - 1, 1), 1);
    EXPECT_EQ(bin_search_first_equal(arr2, 0, test_ele_count - 1, 12), -1);
}