A binary search with C++:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| template<class T>
int bin_search(vector<T>& arr, T target) {
int left = 0, right = arr.size() - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (arr[mid] == target) {
break;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left;
}
|
The same thing with Rust:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| fn bin_search<T: Ord>(arr: &Vec<T>, target: &T) -> usize {
let mut left = 0;
let mut right = arr.len() - 1;
while left <= right {
let mid = (left + right) / 2;
if arr[mid] == *target {
break;
} else if arr[mid] < *target {
left = mid + 1;
} else {
right = mid - 1;
}
}
left
}
|
And with Python:
1
2
3
4
5
6
7
8
9
10
11
12
| def bin_search(arr: list, target):
left = 0
right = len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
break
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return left
|