11#### Summary
22A direct application of the Binary Search algorithm.
33
4+ #### Complexity
5+ * Time complexity: O(log n).
6+ * Space complexity: O(1).
47
5- #### Template of Binary Search [ Pseudo Code]
6- ```
7- int binary_search(int[] arr, int target){
8- int left = ..., right = ... ;
9- while (...){
10- int mid = (right - left) / 2 + left;
11- if (arr[mid] == target){
12- ...
13- }
14- else if (arr[mid] < target){
15- left = ...
16- }
17- else if (arr[mid] > target){
18- right = ...
19- }
20- }
21- return ...
8+ #### Template of Binary Search (in C++)
9+ ```
10+ // Return the index if the target value could be found in the array,
11+ // otherwise, return -1;
12+ int binary_search(vector<int> arr, int target) {
13+ int left = 0, right = arr.size() - 1;
14+ while(left <= right) {
15+ int mid = (right - left) / 2 + left;
16+ if (arr[mid] == target) {
17+ return mid;
18+ }
19+ else if (arr[mid] > target){
20+ right = mid - 1;
21+ }
22+ else if (arr[mid] < target){
23+ left = mid + 1;
24+ }
25+ }
26+ return -1;
2227}
28+ ```
29+
30+ #### Other variants
31+
32+ 1 . Left bound. Find the first index i such that arr[ i] == target, otherwise return -1.
33+
34+ * Using half-closed interval [ L, R).
2335```
36+ int left_bound_binary_Search(vector<int> arr, int target) {
37+ int left = 0, right = arr.size();
38+ while(left < right) {
39+ int mid = (right - left) / 2 + left;
40+ if (arr[mid] == target) {
41+ right = mid;
42+ }
43+ else if (arr[mid] > target){
44+ right = mid;
45+ }
46+ else if (arr[mid] < target){
47+ left = mid + 1;
48+ }
49+ }
2450
25- #### Remarks
51+ if (left >= arr.size()) return -1;
52+ return (arr[left] == target ? left : -1);
53+ }
54+ ```
55+
56+ * Using closed inteval [ L, R]
57+ ```
58+ int left_bound_binary_Search(vector<int> arr, int target) {
59+ int left = 0, right = arr.size() - 1;
60+ while(left <= right) {
61+ int mid = (right - left) / 2 + left;
62+ if (arr[mid] == target) {
63+ right = mid - 1;
64+ }
65+ else if (arr[mid] > target){
66+ right = mid - 1;
67+ }
68+ else if (arr[mid] < target){
69+ left = mid + 1;
70+ }
71+ }
72+
73+ if (left >= arr.size()) return -1;
74+ return (arr[left] == target ? left : -1);
75+ }
76+ ```
77+
78+ 2 . Right bound. Find the last index i such that arr[ i] == target, otherwise return -1.
2679
80+ * Using half-closed interval [ L, R).
81+ ```
82+ int right_bound_binary_Search(vector<int> arr, int target) {
83+ int left = 0, right = arr.size();
84+ while(left < right) {
85+ int mid = (right - left) / 2 + left;
86+ if (arr[mid] == target) {
87+ left = mid + 1;
88+ }
89+ else if (arr[mid] > target){
90+ right = mid - 1;
91+ }
92+ else if (arr[mid] < target){
93+ left = mid + 1;
94+ }
95+ }
96+ if (left == 0) return -1;
97+ else return (arr[left - 1] == target ? (left - 1) : -1);
98+ }
99+ ```
100+
101+ * Using closed inteval [ L, R]
102+ ```
103+ int right_bound_binary_Search(vector<int> arr, int target) {
104+ int left = 0, right = arr.size() - 1;
105+ while(left <= right) {
106+ int mid = (right - left) / 2 + left;
107+ if (arr[mid] == target) {
108+ left = mid + 1;
109+ }
110+ else if (arr[mid] > target){
111+ right = mid - 1;
112+ }
113+ else if (arr[mid] < target){
114+ left = mid + 1;
115+ }
116+ }
117+
118+ if (right < 0) return -1;
119+ return (arr[right] == target ? right : -1);
120+ }
121+ ```
122+
123+
124+ These templates are also available [ here] ( https://github.com/jinshendan/Leetcode/tree/master/Template/Maths/Binary-Search ) .
125+
126+
127+ #### Remarks
27128* Use
28129```
29130mid = (right - left) / 2 + left
@@ -32,5 +133,4 @@ instead of
32133```
33134mid = (left + right) / 2
34135```
35- to avoid any overflow in intermediare calculation.
36- *
136+ to avoid any overflow in intermediare calculation.
0 commit comments