BinarySearch::lowerBound() - Code Metrics - yoanm/php-common-dsa - Measure and Improve Code Quality continuously with Scrutinizer

BinarySearch::lowerBound() A
last analyzed 2025-10-30 10:15 UTC

↳ Parent: BinarySearch

Complexity

Conditions	3
Paths	3

Size

Total Lines	23
Code Lines	8

Duplication

Lines	0
Ratio	0 %

Code Coverage

Tests	8
CRAP Score	3

Importance

Changes	1
Bugs	0	Features	0

Metric	Value
cc	3
eloc	8
c	1
b	0
f	0
nc	3
nop	4
dl	0
loc	23
ccs	8
cts	8
cp	1
crap	3
rs	10

<?php

declare(strict_types=1);

namespace Yoanm\CommonDSA\Algorithm;

class BinarySearch
{
    /**
     * Find an index where value is equal to $target
     *
     *
     * ### Time/Space complexity
     * With:
     * - 𝑛 equals the provided list length.
     *
     * TC: 𝑂⟮㏒ 𝑛⟯ - classic for binary search
     *
     * SC: 𝑂⟮𝟷⟯ - Constant extra space
     *
     *
     * @template TValue of (int|float)
     *
     *
     * @param array<int|float> $list ⚠ Must be a 0 indexed list, 0 to n consecutive indexes, sorted in non-decreasing
     *                               order (min→max)!<br>
     *                               May contain duplicates.
     * @phpstan-param list<TValue> $list
     * @phpstan-param TValue $target
     * @param int $headIdx Lookup start index.<br>
     *                     Default to 0 (head index).
     * @param int|null $tailIdx Lookup end index.<br>
     *                          Default to tail index
     *
     * @return int Index where $target has been found, -1 if not found
     */
    public static function find(
        array $list,
        int|float $target,
        int $headIdx = 0,
        int|null $tailIdx = null,
    ): int {
        $tailIdx ??= count($list) - 1;

        while ($headIdx <= $tailIdx) {
            // Prevent ($lowIdx + $highIdx) overflow !
            $midIdx = $headIdx + (($tailIdx - $headIdx) >> 1);

            if ($list[$midIdx] < $target) {
                // Current value is too small ? => Ignore left side and current
                $headIdx = $midIdx + 1;
            } elseif ($list[$midIdx] > $target) {
                // Current value is greater ? => Ignore right side and current
                $tailIdx = $midIdx - 1;
            } else {
                return $midIdx;
            }
        }

        return -1;
    }

    /**
     * Finds the index of left-most element which is greater than or equal to $target (=not strictly lower than $target)
     *
     *
     * ### Time/Space complexity
     * With:
     * - 𝑛 equals the provided list length.
     *
     * TC: 𝑂⟮㏒ 𝑛⟯ - classic for binary search
     *
     * SC: 𝑂⟮𝟷⟯ - Constant extra space
     *
     *
     * @template TValue of (int|float)
     *
     *
     * @param array<int|float> $list ⚠ Must be a 0 indexed list, 0 to n consecutive indexes, sorted in non-decreasing
     *                               order (min→max)!<br>
     *                               May contain duplicates.
     * @phpstan-param list<TValue> $list
     * @phpstan-param TValue $target
     * @param int $lowIdx Lookup start index.<br>
     *                    Default to 0 (head index).
     * @param int|null $highIdx Lookup end index.<br>
     *                          Default to $list length (=tail index + 1)
     *
     * @return int Index where $target can be inserted in $list while keeping it sorted.<br>
     *             ⚠ Might be beyond $list current indexes if $target is greater than tail value !
     */
    public static function lowerBound(
        array $list,
        int|float $target,
        int $lowIdx = 0,
        int|null $highIdx = null,
    ): int {
        $highIdx ??= count($list);

        while ($lowIdx < $highIdx) {
            // Prevent ($lowIdx + $highIdx) overflow !
            $midIdx = $lowIdx + (($highIdx - $lowIdx) >> 1);

            if ($list[$midIdx] < $target) {
                // Current value is too small ? => Ignore left side and current
                $lowIdx = $midIdx + 1;
            } else {
                // Current value is either equal or greater ?
                // => Ignore right side BUT keep current (might be the right index)
                $highIdx = $midIdx;
            }
        }

        return $lowIdx;
    }

    /**
     * Finds the index of left-most element which is strictly greater than $target
     *
     *
     * ### Time/Space complexity
     * With:
     * - 𝑛 equals the provided list length.
     *
     * TC: 𝑂⟮㏒ 𝑛⟯ - classic for binary search
     *
     * SC: 𝑂⟮𝟷⟯ - Constant extra space
     *
     *
     * @template TValue of (int|float)
     *
     *
     * @param array<int|float> $list ⚠ Must be a 0 indexed list, 0 to n consecutive indexes, sorted in non-decreasing
     *                               order (min→max)!<br>
     *                               May contain duplicates.
     * @phpstan-param list<TValue> $list
     * @phpstan-param TValue $target
     * @param int $lowIdx Lookup start index.<br>
     *                    Default to 0 (head index).
     * @param int|null $highIdx Lookup end index.<br>
     *                          Default to $list length (=tail index + 1)
     *
     * @return int Index where $target can be inserted in $list while keeping it sorted.<br>
     *             ⚠ Might be beyond $list current indexes if $target is greater than or equal to tail value !
     */
    public static function upperBound(
        array $list,
        int|float $target,
        int $lowIdx = 0,
        int|null $highIdx = null,
    ): int {
        $highIdx ??= count($list);

        while ($lowIdx < $highIdx) {
            // Prevent ($lowIdx + $highIdx) overflow !
            $middleIdx = $lowIdx + (($highIdx - $lowIdx) >> 1);

            if ($list[$middleIdx] <= $target) {
                // Current value is either equal or too small ? => Ignore left side and current
                $lowIdx = $middleIdx + 1;
            } else {
                // Current value is greater ? => Ignore right side BUT keep current (might be the right index)
                $highIdx = $middleIdx;
            }
        }

        return $lowIdx;
    }
}


1		<?php
2
3		declare(strict_types=1);
4
5		namespace Yoanm\CommonDSA\Algorithm;
6
7		class BinarySearch
8		{
9		/**
10		* Find an index where value is equal to $target
11		*
12		*
13		* ### Time/Space complexity
14		* With:
15		* - 𝑛 equals the provided list length.
16		*
17		* TC: 𝑂⟮㏒ 𝑛⟯ - classic for binary search
18		*
19		* SC: 𝑂⟮𝟷⟯ - Constant extra space
20		*
21		*
22		* @template TValue of (int\|float)
23		*
24		*
25		* @param array<int\|float> $list ⚠ Must be a 0 indexed list, 0 to n consecutive indexes, sorted in non-decreasing
26		* order (min→max)!<br>
27		* May contain duplicates.
28		* @phpstan-param list<TValue> $list
29		* @phpstan-param TValue $target
30		* @param int $headIdx Lookup start index.<br>
31		* Default to 0 (head index).
32		* @param int\|null $tailIdx Lookup end index.<br>
33		* Default to tail index
34		*
35		* @return int Index where $target has been found, -1 if not found
36		*/
37	5	public static function find(
38		array $list,
39		int\|float $target,
40		int $headIdx = 0,
41		int\|null $tailIdx = null,
42		): int {
43	5	$tailIdx ??= count($list) - 1;
44
45	5	while ($headIdx <= $tailIdx) {
46		// Prevent ($lowIdx + $highIdx) overflow !
47	4	$midIdx = $headIdx + (($tailIdx - $headIdx) >> 1);
48
49	4	if ($list[$midIdx] < $target) {
50		// Current value is too small ? => Ignore left side and current
51	4	$headIdx = $midIdx + 1;
52	4	} elseif ($list[$midIdx] > $target) {
53		// Current value is greater ? => Ignore right side and current
54	3	$tailIdx = $midIdx - 1;
55		} else {
56	2	return $midIdx;
57		}
58		}
59
60	3	return -1;
61		}
62
63		/**
64		* Finds the index of left-most element which is greater than or equal to $target (=not strictly lower than $target)
65		*
66		*
67		* ### Time/Space complexity
68		* With:
69		* - 𝑛 equals the provided list length.
70		*
71		* TC: 𝑂⟮㏒ 𝑛⟯ - classic for binary search
72		*
73		* SC: 𝑂⟮𝟷⟯ - Constant extra space
74		*
75		*
76		* @template TValue of (int\|float)
77		*
78		*
79		* @param array<int\|float> $list ⚠ Must be a 0 indexed list, 0 to n consecutive indexes, sorted in non-decreasing
80		* order (min→max)!<br>
81		* May contain duplicates.
82		* @phpstan-param list<TValue> $list
83		* @phpstan-param TValue $target
84		* @param int $lowIdx Lookup start index.<br>
85		* Default to 0 (head index).
86		* @param int\|null $highIdx Lookup end index.<br>
87		* Default to $list length (=tail index + 1)
88		*
89		* @return int Index where $target can be inserted in $list while keeping it sorted.<br>
90		* ⚠ Might be beyond $list current indexes if $target is greater than tail value !
91		*/
92	16	public static function lowerBound(
93		array $list,
94		int\|float $target,
95		int $lowIdx = 0,
96		int\|null $highIdx = null,
97		): int {
98	16	$highIdx ??= count($list);
99
100	16	while ($lowIdx < $highIdx) {
101		// Prevent ($lowIdx + $highIdx) overflow !
102	15	$midIdx = $lowIdx + (($highIdx - $lowIdx) >> 1);
103
104	15	if ($list[$midIdx] < $target) {
105		// Current value is too small ? => Ignore left side and current
106	10	$lowIdx = $midIdx + 1;
107		} else {
108		// Current value is either equal or greater ?
109		// => Ignore right side BUT keep current (might be the right index)
110	13	$highIdx = $midIdx;
111		}
112		}
113
114	16	return $lowIdx;
115		}
116
117		/**
118		* Finds the index of left-most element which is strictly greater than $target
119		*
120		*
121		* ### Time/Space complexity
122		* With:
123		* - 𝑛 equals the provided list length.
124		*
125		* TC: 𝑂⟮㏒ 𝑛⟯ - classic for binary search
126		*
127		* SC: 𝑂⟮𝟷⟯ - Constant extra space
128		*
129		*
130		* @template TValue of (int\|float)
131		*
132		*
133		* @param array<int\|float> $list ⚠ Must be a 0 indexed list, 0 to n consecutive indexes, sorted in non-decreasing
134		* order (min→max)!<br>
135		* May contain duplicates.
136		* @phpstan-param list<TValue> $list
137		* @phpstan-param TValue $target
138		* @param int $lowIdx Lookup start index.<br>
139		* Default to 0 (head index).
140		* @param int\|null $highIdx Lookup end index.<br>
141		* Default to $list length (=tail index + 1)
142		*
143		* @return int Index where $target can be inserted in $list while keeping it sorted.<br>
144		* ⚠ Might be beyond $list current indexes if $target is greater than or equal to tail value !
145		*/
146	16	public static function upperBound(
147		array $list,
148		int\|float $target,
149		int $lowIdx = 0,
150		int\|null $highIdx = null,
151		): int {
152	16	$highIdx ??= count($list);
153
154	16	while ($lowIdx < $highIdx) {
155		// Prevent ($lowIdx + $highIdx) overflow !
156	15	$middleIdx = $lowIdx + (($highIdx - $lowIdx) >> 1);
157
158	15	if ($list[$middleIdx] <= $target) {
159		// Current value is either equal or too small ? => Ignore left side and current
160	13	$lowIdx = $middleIdx + 1;
161		} else {
162		// Current value is greater ? => Ignore right side BUT keep current (might be the right index)
163	10	$highIdx = $middleIdx;
164		}
165		}
166
167	16	return $lowIdx;
168		}
169		}
170

yoanm / php-common-dsa

BinarySearch::lowerBound() A last analyzed 2025-10-30 10:15 UTC

Complexity

Size

Duplication

Code Coverage

Importance

Duplication Side-by-Side

Filter issues like

BinarySearch::lowerBound() A
last analyzed 2025-10-30 10:15 UTC