forked from TheAlgorithms/PHP
-
Notifications
You must be signed in to change notification settings - Fork 0
/
LowerBound.php
37 lines (32 loc) · 913 Bytes
/
LowerBound.php
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
<?php
require_once __DIR__ . '/../vendor/autoload.php';
require_once __DIR__ . '/../Utils/ArrayHelpers.php';
/**
* Lower Bound of an element is minimum index that an element would be placed
* if it is added into that sorted array
*
* [C++ Lower Bound](http://www.cplusplus.com/reference/algorithm/lower_bound/)
*
* It is assumed that an integer array is provided
* and the second parameter is also an integer
*
* @param array $arr of sorted integers
* @param integer $elem whose lower bound is to be found
*
* @return int the index of lower bound of the given element
*/
function lowerBound(array $arr, int $elem)
{
isSortedAscendingInts($arr);
$hi = count($arr);
$lo = 0;
while ($lo < $hi) {
$mid = $lo + floor(($hi - $lo) / 2);
if ($arr[$mid] < $elem) {
$lo = $mid + 1;
} else {
$hi = $mid;
}
}
return $lo;
}