Skip to content

Commit 3d406b3

Browse files
liuyuboboboliuyubobobo
committed
Chapter 05 section 04 added.
1 parent 9a18bc0 commit 3d406b3

File tree

8 files changed

+421
-1
lines changed

8 files changed

+421
-1
lines changed

‎05-Binary-Search-Tree/Course Code (C++)/Optional-04-More-about-Binary-Search/BinarySearch.h

Lines changed: 95 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,95 @@
1+
//
2+
// Created by liuyubobobo on 11/21/17.
3+
//
4+
5+
#ifndef OPTIONAL_03_LOWER_BOUND_AND_UPPER_BOUND_IN_BINARY_SEARCH_BINARYSEARCH_H
6+
#define OPTIONAL_03_LOWER_BOUND_AND_UPPER_BOUND_IN_BINARY_SEARCH_BINARYSEARCH_H
7+
8+
#include <cassert>
9+
10+
using namespace std;
11+
12+
namespace BinarySearch{
13+
14+
// 二分查找法, 在一个有序数组arr中, 寻找大于等于target的元素的第一个索引
15+
// 如果存在, 则返回相应的索引index
16+
// 否则, 返回arr的元素个数 n
17+
// 相当于 lower_bound
18+
template<typename T>
19+
int firstGreaterOrEqual(T arr[], int n, T target){
20+
21+
assert(n >= 0);
22+
23+
int l = 0, r = n;
24+
while(l != r){
25+
int mid = l + (r - l) / 2;
26+
if(arr[mid] < target)
27+
l = mid + 1;
28+
else // nums[mid] >= target
29+
r = mid;
30+
}
31+
return l;
32+
}
33+
34+
// 二分查找法, 在一个有序数组arr中, 寻找大于target的元素的第一个索引
35+
// 如果存在, 则返回相应的索引index
36+
// 否则, 返回arr的元素个数 n
37+
// 相当于 upper_bound
38+
template<typename T>
39+
int firstGreaterThan(T arr[], int n, T target){
40+
41+
assert(n >= 0);
42+
43+
int l = 0, r = n;
44+
while(l != r){
45+
int mid = l + (r - l) / 2;
46+
if(arr[mid] <= target)
47+
l = mid + 1;
48+
else // nums[mid] > target
49+
r = mid;
50+
}
51+
return l;
52+
}
53+
54+
// 二分查找法, 在一个有序数组arr中, 寻找小于等于target的元素的最大索引
55+
// 如果存在, 则返回相应的索引index
56+
// 否则, 返回 -1
57+
template<typename T>
58+
int lastLessOrEqual(T arr[], int n, T target){
59+
60+
assert(n >= 0);
61+
62+
int l = -1, r = n - 1;
63+
while(l != r){
64+
int mid = l + (r - l + 1) / 2;
65+
if(arr[mid] > target)
66+
r = mid - 1;
67+
else // nums[mid] <= target
68+
l = mid;
69+
}
70+
71+
return l;
72+
}
73+
74+
// 二分查找法, 在一个有序数组arr中, 寻找小于target的元素的最大索引
75+
// 如果存在, 则返回相应的索引index
76+
// 否则, 返回 -1
77+
template<typename T>
78+
int lastLessThan(T arr[], int n, T target){
79+
80+
assert(n >= 0);
81+
82+
int l = -1, r = n - 1;
83+
while(l != r){
84+
int mid = l + (r - l + 1) / 2;
85+
if(arr[mid] >= target)
86+
r = mid - 1;
87+
else // nums[mid] < target
88+
l = mid;
89+
}
90+
91+
return l;
92+
}
93+
}
94+
95+
#endif //OPTIONAL_03_LOWER_BOUND_AND_UPPER_BOUND_IN_BINARY_SEARCH_BINARYSEARCH_H

‎05-Binary-Search-Tree/Course Code (C++)/Optional-04-More-about-Binary-Search/CMakeLists.txt

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,7 @@
1+
cmake_minimum_required(VERSION 3.5)
2+
project(Optional_04_More_about_Binary_Search)
3+
4+
set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -std=c++11")
5+
6+
set(SOURCE_FILES main.cpp)
7+
add_executable(Optional_04_More_about_Binary_Search ${SOURCE_FILES})

‎05-Binary-Search-Tree/Course Code (C++)/Optional-04-More-about-Binary-Search/LinearSearch.h

Lines changed: 75 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,75 @@
1+
//
2+
// Created by liuyubobobo on 11/21/17.
3+
//
4+
5+
#ifndef OPTIONAL_03_LOWER_BOUND_AND_UPPER_BOUND_IN_BINARY_SEARCH_LINEARSEARCH_H
6+
#define OPTIONAL_03_LOWER_BOUND_AND_UPPER_BOUND_IN_BINARY_SEARCH_LINEARSEARCH_H
7+
8+
#include <cassert>
9+
10+
using namespace std;
11+
12+
namespace LinearSearch{
13+
14+
// 线性查找法, 在一个有序数组arr中, 寻找大于等于target的元素的第一个索引
15+
// 如果存在, 则返回相应的索引index
16+
// 否则, 返回arr的元素个数 n
17+
// 相当于 lower_bound
18+
template<typename T>
19+
int firstGreaterOrEqual(T arr[], int n, T target){
20+
21+
assert(n >= 0);
22+
23+
for(int i = 0 ; i < n ; i ++)
24+
if(arr[i] >= target)
25+
return i;
26+
return n;
27+
}
28+
29+
// 线性查找法, 在一个有序数组arr中, 寻找大于target的元素的第一个索引
30+
// 如果存在, 则返回相应的索引index
31+
// 否则, 返回arr的元素个数 n
32+
// 相当于 upper_bound
33+
template<typename T>
34+
int firstGreaterThan(T arr[], int n, T target){
35+
36+
assert(n >= 0);
37+
38+
for(int i = 0 ; i < n ; i ++)
39+
if(arr[i] > target)
40+
return i;
41+
return n;
42+
}
43+
44+
// 线性查找法, 在一个有序数组arr中, 寻找小于等于target的元素的最大索引
45+
// 如果存在, 则返回相应的索引index
46+
// 否则, 返回 -1
47+
template<typename T>
48+
int lastLessOrEqual(T arr[], int n, T target){
49+
50+
assert(n >= 0);
51+
52+
for(int i = 0 ; i < n ; i ++)
53+
if(arr[i] > target)
54+
return i - 1;
55+
56+
return n - 1;
57+
}
58+
59+
// 线性查找法, 在一个有序数组arr中, 寻找小于target的元素的最大索引
60+
// 如果存在, 则返回相应的索引index
61+
// 否则, 返回 -1
62+
template<typename T>
63+
int lastLessThan(T arr[], int n, T target){
64+
65+
assert(n >= 0);
66+
67+
for(int i = 0 ; i < n ; i ++)
68+
if(arr[i] >= target)
69+
return i - 1;
70+
71+
return n - 1;
72+
}
73+
}
74+
75+
#endif //OPTIONAL_03_LOWER_BOUND_AND_UPPER_BOUND_IN_BINARY_SEARCH_LINEARSEARCH_H

‎05-Binary-Search-Tree/Course Code (C++)/Optional-04-More-about-Binary-Search/main.cpp

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
#include <iostream>
2+
#include <cassert>
3+
#include <cstdlib>
4+
#include <ctime>
5+
#include "BinarySearch.h"
6+
#include "LinearSearch.h"
7+
8+
using namespace std;
9+
10+
int* generateRandomOrderedArray(int n, int rangeL, int rangeR){
11+
12+
int* arr = new int[n];
13+
14+
srand(time(NULL));
15+
for(int i = 0 ; i < n ; i ++)
16+
arr[i] = rand() % (rangeR - rangeL + 1) + rangeL;
17+
sort(arr, arr + n);
18+
return arr;
19+
}
20+
21+
int main() {
22+
23+
int n = 1000;
24+
int m = 100;
25+
int* arr = generateRandomOrderedArray(n, 0, m);
26+
27+
/// 我们使用简单的线性查找法来验证我们写的二分查找法
28+
for(int i = -1 ; i <= m + 1 ; i ++) {
29+
assert(BinarySearch::firstGreaterOrEqual(arr, n, i) ==
30+
LinearSearch::firstGreaterOrEqual(arr, n, i));
31+
assert(BinarySearch::firstGreaterThan(arr, n, i) ==
32+
LinearSearch::firstGreaterThan(arr, n, i));
33+
assert(BinarySearch::lastLessOrEqual(arr, n, i) ==
34+
LinearSearch::lastLessOrEqual(arr, n, i));
35+
assert(BinarySearch::lastLessThan(arr, n, i) ==
36+
LinearSearch::lastLessThan(arr, n, i));
37+
}
38+
39+
cout << "test completed:)" << endl;
40+
41+
return 0;
42+
}

‎05-Binary-Search-Tree/Course Code (Java)/Optional-04-More-about-Binary-Search/src/BinarySearch.java

Lines changed: 87 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,87 @@
1+
/**
2+
* Created by liuyubobobo on 11/21/17.
3+
*/
4+
public class BinarySearch {
5+
6+
private BinarySearch(){}
7+
8+
// 二分查找法, 在一个有序数组arr中, 寻找大于等于target的元素的第一个索引
9+
// 如果存在, 则返回相应的索引index
10+
// 否则, 返回arr的元素个数 n
11+
// 相当于 lower_bound
12+
public static int firstGreaterOrEqual(Comparable[] arr, Comparable target){
13+
14+
if(arr == null)
15+
throw new IllegalArgumentException("arr can not be null.");
16+
17+
int l = 0, r = arr.length;
18+
while(l != r){
19+
int mid = l + (r - l) / 2;
20+
if(arr[mid].compareTo(target) < 0)
21+
l = mid + 1;
22+
else // nums[mid] >= target
23+
r = mid;
24+
}
25+
return l;
26+
}
27+
28+
// 二分查找法, 在一个有序数组arr中, 寻找大于target的元素的第一个索引
29+
// 如果存在, 则返回相应的索引index
30+
// 否则, 返回arr的元素个数 n
31+
// 相当于 upper_bound
32+
public static int firstGreaterThan(Comparable[] arr, Comparable target){
33+
34+
if(arr == null)
35+
throw new IllegalArgumentException("arr can not be null.");
36+
37+
int l = 0, r = arr.length;
38+
while(l != r){
39+
int mid = l + (r - l) / 2;
40+
if(arr[mid].compareTo(target) <= 0)
41+
l = mid + 1;
42+
else // nums[mid] > target
43+
r = mid;
44+
}
45+
return l;
46+
}
47+
48+
// 二分查找法, 在一个有序数组arr中, 寻找小于等于target的元素的最大索引
49+
// 如果存在, 则返回相应的索引index
50+
// 否则, 返回 -1
51+
public static int lastLessOrEqual(Comparable[] arr, Comparable target){
52+
53+
if(arr == null)
54+
throw new IllegalArgumentException("arr can not be null.");
55+
56+
int l = -1, r = arr.length - 1;
57+
while(l != r){
58+
int mid = l + (r - l + 1) / 2;
59+
if(arr[mid].compareTo(target) > 0)
60+
r = mid - 1;
61+
else // nums[mid] <= target
62+
l = mid;
63+
}
64+
65+
return l;
66+
}
67+
68+
// 二分查找法, 在一个有序数组arr中, 寻找小于target的元素的最大索引
69+
// 如果存在, 则返回相应的索引index
70+
// 否则, 返回 -1
71+
public static int lastLessThan(Comparable[] arr, Comparable target){
72+
73+
if(arr == null)
74+
throw new IllegalArgumentException("arr can not be null.");
75+
76+
int l = -1, r = arr.length - 1;
77+
while(l != r){
78+
int mid = l + (r - l + 1) / 2;
79+
if(arr[mid].compareTo(target) >= 0)
80+
r = mid - 1;
81+
else // nums[mid] < target
82+
l = mid;
83+
}
84+
85+
return l;
86+
}
87+
}

‎05-Binary-Search-Tree/Course Code (Java)/Optional-04-More-about-Binary-Search/src/LinearSearch.java

Lines changed: 69 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,69 @@
1+
/**
2+
* Created by liuyubobobo on 11/21/17.
3+
*/
4+
public class LinearSearch {
5+
6+
private LinearSearch(){}
7+
8+
// 线性查找法, 在一个有序数组arr中, 寻找大于等于target的元素的第一个索引
9+
// 如果存在, 则返回相应的索引index
10+
// 否则, 返回arr的元素个数 n
11+
// 相当于 lower_bound
12+
public static int firstGreaterOrEqual(Comparable[] arr, Comparable target){
13+
14+
if(arr == null)
15+
throw new IllegalArgumentException("arr can not be null.");
16+
17+
for(int i = 0 ; i < arr.length ; i ++)
18+
if(arr[i].compareTo(target) >= 0)
19+
return i;
20+
21+
return arr.length;
22+
}
23+
24+
// 线性查找法, 在一个有序数组arr中, 寻找大于target的元素的第一个索引
25+
// 如果存在, 则返回相应的索引index
26+
// 否则, 返回arr的元素个数 n
27+
// 相当于 upper_bound
28+
public static int firstGreaterThan(Comparable[] arr, Comparable target){
29+
30+
if(arr == null)
31+
throw new IllegalArgumentException("arr can not be null.");
32+
33+
for(int i = 0 ; i < arr.length ; i ++)
34+
if(arr[i].compareTo(target) > 0)
35+
return i;
36+
37+
return arr.length;
38+
}
39+
40+
// 线性查找法, 在一个有序数组arr中, 寻找小于等于target的元素的最大索引
41+
// 如果存在, 则返回相应的索引index
42+
// 否则, 返回 -1
43+
public static int lastLessOrEqual(Comparable[] arr, Comparable target){
44+
45+
if(arr == null)
46+
throw new IllegalArgumentException("arr can not be null.");
47+
48+
for(int i = 0 ; i < arr.length ; i ++)
49+
if(arr[i].compareTo(target) > 0)
50+
return i - 1;
51+
52+
return arr.length - 1;
53+
}
54+
55+
// 线性查找法, 在一个有序数组arr中, 寻找小于target的元素的最大索引
56+
// 如果存在, 则返回相应的索引index
57+
// 否则, 返回 -1
58+
public static int lastLessThan(Comparable[] arr, Comparable target){
59+
60+
if(arr == null)
61+
throw new IllegalArgumentException("arr can not be null.");
62+
63+
for(int i = 0 ; i < arr.length ; i ++)
64+
if(arr[i].compareTo(target) >= 0)
65+
return i - 1;
66+
67+
return arr.length - 1;
68+
}
69+
}

0 commit comments

Comments
 (0)