해당 값을 빠르게 검색하는 방법

PHP 인덱스 배열입니다. 배열의 값은 1부터 100까지의 정수(비반복)이며 값이 간헐적으로 나타날 수 있습니다. 즉, 7과 9는 있을 수 있지만 8은 없을 수 있습니다. 그리고 순서가 어긋나는 것, 즉 1부터 100까지 배열되어 있지 않은 것입니다

이제 $a=50이라고 가정하면 ==$a 또는 $a에 가장 가까운 두 값을 빠르게 꺼내는 방법은 무엇일까요?

그런데 배열의 값이 반드시 $a와 같지 않을 수도 있습니다

답글 내용:

PHP 인덱스 배열입니다. 배열의 값은 1부터 100까지의 정수(비반복)이며 값이 간헐적으로 나타날 수 있습니다. 즉, 7과 9는 있을 수 있지만 8은 없을 수 있습니다. 그리고 순서가 어긋나는 것, 즉 1부터 100까지 배열되어 있지 않은 것입니다

이제 $a=50이라고 가정하면 ==$a 또는 $a에 가장 가까운 두 값을 빠르게 꺼내는 방법은 무엇일까요?

그런데 배열의 값이 반드시 $a와 같지 않을 수도 있습니다

1. array_search — 배열에서 주어진 값을 검색하고 성공하면 해당 키 이름을 반환합니다.

2. 은 키 이름을 가져옵니다. $arr[$key-1], $arr[$key+1]은

일 수 있습니다.

위의 것은 매우 간단하지만, 숫자를 찾지 못하면 가장 가까운 것을 찾으세요. 원래 배열의 순서가 엉망이므로 위쪽과 아래쪽이 반드시 가장 가까운 것은 아닙니다. , 2점 검색도 아이디어입니다. 제 아이디어는 먼저 배럴 정렬(현재 알고 있는 양의 정수를 정렬하는 가장 빠른 방법)을 사용하는 것입니다.

<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>

얼마나 효율적인지 모르겠습니다

<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>

수정 없는 정적 쿼리

• 정렬(오름차순), 복잡도 nlogn(1개 정렬)

• 두 지점으로 빠른 위치 지정, 복잡도 logn(쿼리 1개)

<code class="php">// 在有序数组$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));</code>

순서를 변경하지 않고 추가 작업만 수행하는 동적 쿼리

1-100에는 100개의 숫자가 있고, 그 값도 1-100입니다. 69의 위치에 대한 첨자를 구하면 69를 중심으로 하고 이진 탐색을 통해 그 근처 지점의 첨자를 찾을 수 있습니다. 특정 위치에 숫자가 있으면 1로 표시하고 그렇지 않으면 0으로 표시한 다음 69를 중심으로 왼쪽으로 이등분하여 가장 긴 간격을 찾고 합은 0이 되며 오른쪽으로 이등분하여 숫자를 찾습니다. 가장 긴 간격이고 합계는 0입니다. 트리를 사용하면 간격 합계를 빠르게 찾을 수 있습니다. 배열과 마찬가지로 업데이트 쿼리의 복잡도는 로그이고 숫자 추가의 복잡도는 로그입니다.
요구사항 및 목적:

• 트리 배열은 간격 플래그 합계(특정 간격의 값이 나타나는지 여부)를 저장하고 업데이트 및 쿼리 복잡도는 로그됩니다

• 특정 값에 가장 가까운 값을 중심으로 찾아 첨자, 이진 탐색, 복잡도 로그 반환

• 시간에 맞춰 공간을 교환하고 값->첨자 매핑을 저장합니다.

• 배열 끝에 숫자를 추가할 수 있으며 순서대로 추가할 필요는 없습니다.

다음 코드는 다음 문제를 해결합니다

[5,9,3,8,7,10,12] 배열이 있다고 가정합니다.
12에 가장 가까운 좌표를 요청하고 6을 반환합니다
2에 가장 가까운 좌표를 요청하고, 반환 2
고유번호 15 추가
고유번호 18 추가
고유번호 16 추가
고유번호 13 추가
13에 가장 가까운 좌표를 물어보고 10을 반환
17에 가장 가까운 좌표를 요청하고 9를 반환합니다

<code class="php">// 树状数组初始化长度为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，是最大的数</code>

추가 및 삭제 작업이 포함된 동적 쿼리(더 큰 숫자)

첨자가 차지하는 추가 간격 값을 유지한 다음 균형 이진 트리를 설정하고 복잡성 로그n을 쿼리하고 복잡성 로그n을 추가 및 삭제해야 합니다.