一、二分查找
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
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 的值
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
// 查找第一个大于目标的元素 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 的值
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
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 的值
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
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 的值
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
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 测试案例
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
// 测试案例：二分搜索 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); } |