How to quickly retrieve the corresponding value

A PHP index array, the values ​​in the array are integers from 1 to 100 (not repeated), and the values ​​may be intermittent, that is, there may be 7, 9 but not 8. And the order is disrupted, that is, it is not arranged from 1 to 100

Now assuming $a=50, how to quickly get out ==$a or the two values ​​closest to $a?

By the way, the values ​​in the array may not necessarily be equal to $a

Reply content:

A PHP index array, the values ​​in the array are integers from 1 to 100 (not repeated), and the values ​​may be intermittent, that is, there may be 7, 9 but not 8. And the order is disrupted, that is, it is not arranged from 1 to 100

Now assuming $a=50, how to quickly get out ==$a or the two values ​​closest to $a?

By the way, the values ​​in the array may not necessarily be equal to $a

1. array_search — Search for a given value in an array and return the corresponding key if successful

2. Get the key name, $arr[$key-1], $arr[$key+1] can

The one above is very simple, but if the number is not found, find the closest one. The order of the original array is scrambled, so the upper and lower ones are not necessarily the closest. Of course, binary search is also As an idea, I will provide my own algorithmic idea. My idea is to first use barrel sorting (the fastest way to sort positive integers that I currently know)

<code>//这个是要求的数组
$arr = [1,2,3...];

//填充一个1-100范围的数组
$search_arr = array_fill(0 , 99 , 0);

//遍历数组
foreach($search_arr as $k=>$v){
    if(in_array($k , $arr)){
        ++ $v;
    }
}

//此时search_arr数组里面值是1的就是要找的，同时已经排序好了
foreach($search_arr as $k=>$v){
    if($v >= 1){
        $new_arr[] = $k;
    }
}

//此时的new_arr就是一个键从0自增，同时值是排序的数组，然后再结合楼上的写法，便可求出。
</code>

I don’t know how efficient this is

<code>$arr = range(1, 100); // 要求的数组
$target = 10; // 目标值
shuffle($arr); // 打乱顺序

$val_key = array_search($target, $arr);
// 测试 $target 不存在的情况去掉以下注释
// array_splice($arr, $val_key, 1);
// $val_key = '';
if ($val_key) {
    echo "这个值是：{$arr[$val_key]}";
} else {
    sort($arr);
    foreach ($arr as $key => $value) {
        if (($value < $target) && ($arr[$key+1] > $target)) {
            echo "左边：{$value} <br/>";
            echo "右边：{$arr[$key+1]}";
            exit;
        }
    }
}</code>

Static query without modification

• Sort it (ascending order), complexity nlogn (one sorting)

• Then fast positioning by two points, complexity logn (one query)

// 在有序数组$arr中得到大于等于$val的第一个下标
// 如果想要获得离$val最近的值，通过返回值判断
// 如果大于最大的值，返回数组的长度
function binary_search($arr, $val){
    $n = count($arr) - 1;
    $ans = $n + 1;
    $l = 0; $r = $n; 
    while($l <= $r){
        $mid = ($l + $r) >> 1;
        if($arr[$mid] >= $val){
            $ans = $mid;
            $r = $mid -1;
        }
        else $l = $mid + 1;
    }
    return $ans;
}

$arr = [1,5,9,3,8,7,10,12];
sort($arr);
foreach($arr as $key => $val){
    printf("%d ", $val);
}
printf("\n");

$search_num = 6;

printf("%d\n", binary_search($arr, $search_num));

Dynamic query with only add operation, without changing the order

1-100 has 100 numbers, and its value is also 1-100. If you ask for the subscript of the location of 69, you can use 69 as the center and binary search to find the subscript of the point near it. If there is a number at a certain position, Then mark it as 1, otherwise mark it as 0, then take 69 as the center, bisect to the left to find the longest interval and the sum is 0, and bisect to the right to find the longest interval and the sum is 0. You can use a tree array to quickly find the interval sum. , the update query complexity is logn, and the complexity of adding numbers is logn.
Requirements and purposes:

• The tree array saves the interval flag sum (whether the value of a certain interval appears), and the update and query complexity is logn

• Center a certain value to find the value closest to it, and then return its subscript, binary search, complexity logn

• Exchange space for time and save the value->subscript mapping.

• You can add numbers at the end of the array, it is not required to add them in order

The following code solves the following problems

Suppose there is an array [5,9,3,8,7,10,12]
Ask for the coordinate closest to 12, return 6
Ask for the coordinate closest to 2, return 2
Add a non-repeating number 15
Add a non-repeating number 18
Add a non-repeating number 16
Add a non-repeating number 13
Ask for the coordinates closest to 13, return 10
Ask for the coordinates closest to 17, return 9

// 树状数组初始化长度为106，赋空值为0
$arr_bit = array();
for($i = 0;$i <= 105;$i ++){
    $arr_bit[$i] = 0;
}

// 查询1-$x之间的和
function query($x){
    global $arr_bit;
    $sum = 0;
    while($x > 0){
        $sum += $arr_bit[$x];
        $x -= $x & -$x;
    }
    return $sum;
}

// 更新第$x位的标志
function add($x, $val){
    global $arr_bit;
    while($x <= 105){
        $arr_bit[$x] += $val;
        $x += $x & -$x; 
    }
}

$arr = [5,9,3,8,7,10,12];
$arr_tmp = array();
foreach($arr as $key => $val){
    $arr_tmp[$val] = $key;
    printf("%d ",$val);
    add($val, 1);
}
printf("\n");

// 查找离某值最近的下标
// 先查找左边 然后再找右边，若不存在，返回-1
function find_val_pos($val){
    if($val < 1 || $val > 100){
        return -1;
    }
    global $arr_tmp;
    $n = count($arr);
    $l = 1; $r = $val; $ans_l = -1;
    // 得到$val左边最靠近的
    while($l <= $r){
        $mid = ($l + $r) >> 1;
        // 获得$val到$mid的标志区间和
        $mid_val = query($val) - query($mid - 1);
        // 若标志区间和大于1，记录答案，l往右移继续查
        if($mid_val >= 1){
            $ans_l = $mid;
            $l = $mid + 1;
        }
        else $r = $mid - 1;
    }
    $l = $val; $r = 101; $ans_r = -1;
    // 得到$val右边最靠近的
    while($l <= $r){
        $mid = ($l + $r) >> 1;
        // 获得$mid到$val的标志区间和
        $mid_val = query($mid) - query($val - 1);
        if($mid_val >= 1){
            $ans_r = $mid;
            $r = $mid - 1;
        }
        else $l = $mid + 1;
    }
    if($ans_l == -1) return $arr_tmp[$ans_r];
    elseif ($ans_r == -1) return $arr_tmp[$ans_l];
    else {
        if($val - $ans_l > $ans_r - $val)
            return $arr_tmp[$ans_r];
        else
            return $arr_tmp[$ans_l];
    }
}

function add_num($val){
    if($val < 1 || $val > 100) return false;
    global $arr_tmp;
    if(isset($arr_tmp[$val])){
        return false;
    }
    else {
        global $arr;
        $arr_n = count($arr);
        $arr_tmp[$val] = $arr_n;
        $arr[$arr_n] = $val;
        add($val, 1);
        return true;
    }
}

// 查询12最近的坐标
printf("%d\n",find_val_pos(12)); // 结果为6
// 查询2最近的坐标
printf("%d\n",find_val_pos(2));  // 结果为2

add_num(15); // 15位于7
add_num(18); // 18位于8
add_num(16); // 16位于9
add_num(13); // 13位于10

// 查询13最近的坐标
printf("%d\n",find_val_pos(13)); // 结果为10

// 查询17最近的坐标
printf("%d\n",find_val_pos(17)); // 结果为9

// 查询15最近的坐标
printf("%d\n",find_val_pos(15)); // 结果为7

printf("hh\n");
// 查询100最近的坐标
printf("%d\n",find_val_pos(100)); // 结果为8，因为第8个位置是18，是最大的数

Dynamic query with add and delete operations (larger numbers)

You need to maintain an additional interval value occupied by the subscript, and then set a balanced binary tree, query complexity logn, add and delete complexity logn.