Question

How to search insert position of K in a sorted array with PHP

Answer 1

// Given a sorted array/vector/list of distinct integers and a target value K, 
// return the index if the target is found. 
// If not, return the index where it would be if it were inserted in order.

// Function to find the index of k or the position where it should be inserted
function searchInsertPositionOfK($arr, $k) {
    for ($i = 0; $i < count($arr); $i++) {
        // If k is found or needs to be inserted before $arr[$i]
        if ($arr[$i] >= $k) {
            return $i;
        }
    }
    // If k is greater than all elements, it should be inserted at the end
    return count($arr);
}

$arr1 = [1, 3, 5, 6, 7, 8];
$k1 = 5;
echo searchInsertPositionOfK($arr1, $k1) . "\n";

$arr2 = [1, 3, 5, 6, 7, 8];
$k2 = 2;
echo searchInsertPositionOfK($arr2, $k2) . "\n";

$arr3 = [1, 3, 5, 6, 7, 8];
$k3 = 9;
echo searchInsertPositionOfK($arr3, $k3) . "\n";



/*
run:

2
1
6

*/

 

70+ SQL courses for beginners and professionals

Answer 2

// Given a sorted array/vector/list of distinct integers and a target value K, 
// return the index if the target is found. 
// If not, return the index where it would be if it were inserted in order.

// Function to find the index of k or the position where it should be inserted - Using Binary Search
function searchInsertPositionOfK($arr, $k) {
    $left = 0;
    $right = count($arr) - 1;

    while ($left <= $right) {
        $mid = $left + intdiv($right - $left, 2);

        if ($arr[$mid] == $k) {
            return $mid;
        }
        // If k is smaller, search in the left half
        elseif ($arr[$mid] > $k) {
            $right = $mid - 1;
        }
        // If k is larger, search in the right half
        else {
            $left = $mid + 1;
        }
    }

    // If k is not found, return the index where it should be inserted
    return $left;
}

$arr1 = [1, 3, 5, 6, 7, 8];
$k1 = 5;
echo searchInsertPositionOfK($arr1, $k1) . "\n";

$arr2 = [1, 3, 5, 6, 7, 8];
$k2 = 2;
echo searchInsertPositionOfK($arr2, $k2) . "\n";

$arr3 = [1, 3, 5, 6, 7, 8];
$k3 = 9;
echo searchInsertPositionOfK($arr3, $k3) . "\n";



/*
run:

2
1
6

*/

 

70+ SQL courses for beginners and professionals