Skip to content

Commit 9a18bc0

Browse files
liuyuboboboliuyubobobo
committed
Chapter 05 Optional 03 C++ codes updated. Java codes added.
1 parent be14a2a commit 9a18bc0

File tree

7 files changed

+249
-39
lines changed

7 files changed

+249
-39
lines changed

‎05-Binary-Search-Tree/Course Code (C++)/Optional-03-Lower-Bound-and-Upper-Bound-in-Binary-Search/BinarySearch.h

Lines changed: 55 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,55 @@
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+
// 二分查找法, 实现lower_bound
15+
// 即在一个有序数组arr中, 寻找大于等于target的元素的第一个索引
16+
// 如果存在, 则返回相应的索引index
17+
// 否则, 返回arr的元素个数 n
18+
template<typename T>
19+
int lower_bound(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+
// 二分查找法, 实现upper_bound
35+
// 即在一个有序数组arr中, 寻找大于target的元素的第一个索引
36+
// 如果存在, 则返回相应的索引index
37+
// 否则, 返回arr的元素个数 n
38+
template<typename T>
39+
int upper_bound(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+
55+
#endif //OPTIONAL_03_LOWER_BOUND_AND_UPPER_BOUND_IN_BINARY_SEARCH_BINARYSEARCH_H

‎05-Binary-Search-Tree/Course Code (C++)/Optional-03-Lower-Bound-and-Upper-Bound-in-Binary-Search/LinearSearch.h

Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
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+
// 线性查找法, 实现lower_bound
15+
// 即在一个有序数组arr中, 寻找大于等于target的元素的第一个索引
16+
// 如果存在, 则返回相应的索引index
17+
// 否则, 返回arr的元素个数 n
18+
template<typename T>
19+
int lower_bound(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+
// 线性查找法, 实现upper_bound
30+
// 即在一个有序数组arr中, 寻找大于target的元素的第一个索引
31+
// 如果存在, 则返回相应的索引index
32+
// 否则, 返回arr的元素个数 n
33+
template<typename T>
34+
int upper_bound(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+
45+
#endif //OPTIONAL_03_LOWER_BOUND_AND_UPPER_BOUND_IN_BINARY_SEARCH_LINEARSEARCH_H

‎05-Binary-Search-Tree/Course Code (C++)/Optional-03-Lower-Bound-and-Upper-Bound-in-Binary-Search/main.cpp

Lines changed: 27 additions & 38 deletions
Original file line numberDiff line numberDiff line change
@@ -1,49 +1,38 @@
11
#include <iostream>
22
#include <cassert>
3+
#include <cstdlib>
4+
#include <ctime>
5+
#include "BinarySearch.h"
6+
#include "LinearSearch.h"
37

48
using namespace std;
59

6-
// 二分查找法, 实现lower_bound
7-
// 即在一个有序数组arr中, 寻找大于等于target的元素的第一个索引
8-
// 如果存在, 则返回相应的索引index
9-
// 否则, 返回arr的元素个数 n
10-
template<typename T>
11-
int lower_bound(T arr[], int n, T target){
12-
13-
assert(n >= 0);
14-
15-
int l = 0, r = n;
16-
while(l != r){
17-
int mid = l + (r - l) / 2;
18-
if(arr[mid] < target)
19-
l = mid + 1;
20-
else // nums[mid] >= target
21-
r = mid;
22-
}
23-
return l;
24-
}
10+
int* generateRandomOrderedArray(int n, int rangeL, int rangeR){
2511

26-
// 二分查找法, 实现upper_bound
27-
// 即在一个有序数组arr中, 寻找大于target的元素的第一个索引
28-
// 如果存在, 则返回相应的索引index
29-
// 否则, 返回arr的元素个数 n
30-
template<typename T>
31-
int upper_bound(T arr[], int n, T target){
32-
33-
assert(n >= 0);
34-
35-
int l = 0, r = n;
36-
while(l != r){
37-
int mid = l + (r - l) / 2;
38-
if(arr[mid] <= target)
39-
l = mid + 1;
40-
else // nums[mid] > target
41-
r = mid;
42-
}
43-
return l;
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;
4419
}
4520

4621
int main() {
47-
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::lower_bound(arr, n, i) ==
30+
LinearSearch::lower_bound(arr, n, i));
31+
assert(BinarySearch::upper_bound(arr, n, i) ==
32+
LinearSearch::upper_bound(arr, n, i));
33+
}
34+
35+
cout << "test completed:)" << endl;
36+
4837
return 0;
4938
}

‎05-Binary-Search-Tree/Course Code (Java)/Optional-03-Lower-Bound-and-Upper-Bound-in-Binary-Search/src/BinarySearch.java

Lines changed: 47 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,47 @@
1+
/**
2+
* Created by liuyubobobo on 11/21/17.
3+
*/
4+
public class BinarySearch {
5+
6+
private BinarySearch(){}
7+
8+
// 二分查找法, 实现lower_bound
9+
// 即在一个有序数组arr中, 寻找大于等于target的元素的第一个索引
10+
// 如果存在, 则返回相应的索引index
11+
// 否则, 返回arr的元素个数 n
12+
public static int lower_bound(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+
// 二分查找法, 实现upper_bound
29+
// 即在一个有序数组arr中, 寻找大于target的元素的第一个索引
30+
// 如果存在, 则返回相应的索引index
31+
// 否则, 返回arr的元素个数 n
32+
public static int upper_bound(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+
}

‎05-Binary-Search-Tree/Course Code (Java)/Optional-03-Lower-Bound-and-Upper-Bound-in-Binary-Search/src/LinearSearch.java

Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
1+
/**
2+
* Created by liuyubobobo on 11/21/17.
3+
*/
4+
public class LinearSearch {
5+
6+
private LinearSearch(){}
7+
8+
// 线性查找法, 实现lower_bound
9+
// 即在一个有序数组arr中, 寻找大于等于target的元素的第一个索引
10+
// 如果存在, 则返回相应的索引index
11+
// 否则, 返回arr的元素个数 n
12+
public static int lower_bound(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+
// 线性查找法, 实现upper_bound
25+
// 即在一个有序数组arr中, 寻找大于target的元素的第一个索引
26+
// 如果存在, 则返回相应的索引index
27+
// 否则, 返回arr的元素个数 n
28+
public static int upper_bound(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+
}

‎05-Binary-Search-Tree/Course Code (Java)/Optional-03-Lower-Bound-and-Upper-Bound-in-Binary-Search/src/Main.java

Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
import java.util.Arrays;
2+
3+
public class Main {
4+
5+
private Main(){}
6+
7+
private static Integer[] generateRandomOrderedArray(int n, int rangeL, int rangeR){
8+
9+
Integer[] arr = new Integer[n];
10+
11+
for(int i = 0 ; i < n ; i ++)
12+
arr[i] = (int)(Math.random() * (rangeR - rangeL + 1)) + rangeL;
13+
Arrays.sort(arr);
14+
return arr;
15+
}
16+
17+
public static void main(String[] args) {
18+
19+
int n = 1000;
20+
int m = 100;
21+
Integer[] arr = generateRandomOrderedArray(n, 0, m);
22+
23+
/// 我们使用简单的线性查找法来验证我们写的二分查找法
24+
for (int i = -1; i <= m + 1; i++) {
25+
26+
if (BinarySearch.lower_bound(arr, i) != LinearSearch.lower_bound(arr, i))
27+
throw new IllegalArgumentException("lower_bound error!");
28+
29+
if (BinarySearch.upper_bound(arr, i) != LinearSearch.upper_bound(arr, i))
30+
throw new IllegalArgumentException("upper_bound error!");
31+
}
32+
33+
System.out.println("test completed:)");
34+
}
35+
}

‎README.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -121,7 +121,7 @@
121121
| 本章课程最终代码 | [C++源码](https://github.com/liuyubobobo/Play-with-Algorithms/tree/master/05-Binary-Search-Tree/Course%20Code%20(C%2B%2B)/Chapter-05-Completed-Code) | [Java源码](https://github.com/liuyubobobo/Play-with-Algorithms/tree/master/05-Binary-Search-Tree/Course%20Code%20(Java)/Chapter-05-Completed-Code/src/bobo/algo) |
122122
| 补充1 二分查找法改变变量定义，论如何写出正确算法 | [玩转算法面试](http://coding.imooc.com/class/82.html) | [第三章1，2小节](http://coding.imooc.com/lesson/82.html#mid=2656) |
123123
| 补充2 二分搜索法的floor和ceil | [C++源码](https://github.com/liuyubobobo/Play-with-Algorithms/tree/master/05-Binary-Search-Tree/Course%20Code%20(C%2B%2B)/Optional-02-Floor-and-Ceil-in-Binary-Search) | [Java源码](https://github.com/liuyubobobo/Play-with-Algorithms/tree/master/05-Binary-Search-Tree/Course%20Code%20(Java)/Optional-02-Floor-and-Ceil-in-Binary-Search/src/bobo/algo/) |
124-
| 补充3 二分搜索法的lower bound和upper bound | [C++源码](05-Binary-Search-Tree/Course%20Code%20(C%2B%2B)/Optional-03-Lower-Bound-and-Upper-Bound-in-Binary-Search/) | [Java源码][敬请期待] |
124+
| 补充3 二分搜索法的lower bound和upper bound | [C++源码](05-Binary-Search-Tree/Course%20Code%20(C%2B%2B)/Optional-03-Lower-Bound-and-Upper-Bound-in-Binary-Search/) | [Java源码](05-Binary-Search-Tree/Course%20Code%20(Java)/Optional-03-Lower-Bound-and-Upper-Bound-in-Binary-Search/src/) |
125125
| 补充4 二分搜索的总结 | [整理中] | [敬请期待] |
126126
| 补充5 二分搜索树中的floor和ceil | [C++源码](https://github.com/liuyubobobo/Play-with-Algorithms/tree/master/05-Binary-Search-Tree/Course%20Code%20(C%2B%2B)/Optional-05-Floor-and-Ceil-in-BST/) | [Java源码](https://github.com/liuyubobobo/Play-with-Algorithms/tree/master/05-Binary-Search-Tree/Course%20Code%20(Java)/Optional-05-Floor-and-Ceil-in-BST/src/bobo/algo/) |
127127
| 补充6 二分搜索树中的前驱和后继 | [C++源码](https://github.com/liuyubobobo/Play-with-Algorithms/tree/master/05-Binary-Search-Tree/Course%20Code%20(C%2B%2B)/Optional-06-Predecessor-and-Successor-in-BST/) | [Java源码](https://github.com/liuyubobobo/Play-with-Algorithms/tree/master/05-Binary-Search-Tree/Course%20Code%20(Java)/Optional-06-Predecessor-and-Successor-in-BST/src/bobo/algo/) |

0 commit comments

Comments
 (0)