Binary Search Queries
PHP
Hard
5 views
Problem Description
Given a sorted array and q queries, use a function to binary search each query. Print 0-based index or -1.
Input Format
Line1 n q. Line2 n sorted ints. Next q lines x.
Output Format
q lines indices.
Sample Test Case
Input:
5 3
1 3 5 7 9
3
4
9
Official Solution
<?php
$inputText=rtrim(stream_get_contents(STDIN));
if($inputText==='') exit;
$inputLines=preg_split('/\\R/', $inputText);
$first=preg_split('/\\s+/', trim($inputLines[0] ?? ''));
$n=intval($first[0] ?? 0);
$q=intval($first[1] ?? 0);
$arr=array_map('intval',preg_split('/\\s+/', trim($inputLines[1] ?? '')));
function bsearch($a,$x){
$l=0; $r=count($a)-1;
while($l<=$r){
$m=intdiv($l+$r,2);
if($a[$m]===$x) return $m;
if($a[$m]<$x) $l=$m+1; else $r=$m-1;
}
return -1;
}
$output=[];
for($i=0;$i<$q;$i++){
$x=intval(trim($inputLines[$i+2] ?? '0'));
$output[] = strval(bsearch($arr,$x));
}
echo implode(PHP_EOL,$output);
?>
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!