Блог

Сегодня у меня было собеседование, и человек задал мне этот вопрос:

Как вы можете легко найти элемент в отсортированном по кругу массиве

Поскольку я не знал ответа, я попытался найти решение. Вот что у меня есть:

Спасибо

 <?php


function searchincircularsorterlist($a, $len, $num) {
    $start=0;
    $end=$len-1;
    $mid = 0;
    while($start<$end) {
        $mid=$start $end/2;
        if ($num == $a[$mid]) {
            return $num;
        }
        if($num<$a[$mid]) {
            if($num<$a[$start] amp;amp; $a[$start]<=$a[$start 1])
            $start=$mid  ;
            else
            $end=$mid--;
            }
        else {
            if($num>$a[$end] amp;amp; $a[$end-1]<=$a[end])
            $end=$mid--;
            else
            $start=$mid  ;
        }
    }
    if ($start == $end amp;amp; $num == $a[$start]) {
        return $num;
    }
    return -1; 
}

$array = array(7,8,9,0,1,2,3,4,5,6);
var_dump(searchincircularsorterlist($array,sizeof($array),4));
 

Я пытаюсь работать с массивом с круговой сортировкой, но по какой-то причине он не работает. Что не так с моим кодом?

1) изучите приоритет операций. У вас должно быть: $mid=($start $end)/2; в итоге вы разделили $end на 2, а затем $start — результат. Вот почему вы получили бесконечный цикл.

2) используйте: $start=$mid 1; а не $start=$mid ; то, что поможет уменьшить количество петель

 <?php

function searchincircularsorterlist($a, $len, $num) {
    $start=0;
    $end=$len-1;
    $mid = 0;
    while($start<$end) {
        $mid=($start $end)/2;
        if ($num == $a[$mid]) {
            return $num;
        }
        if($num<$a[$mid]) {
            if($num<$a[$start] amp;amp; $a[$start]<=$a[$start 1])
            $start=$mid 1;
            else
            $end=$mid-1;
            }
        else {
            if($num>$a[$end] amp;amp; $a[$end-1]<=$a[end])
            $end=$mid-1;
            else
            $start=$mid 1;
        }
    }
    if ($start == $end amp;amp; $num == $a[$start]) {
        return $num;
    }
    return -1; 
}

$array = array(7,8,9,0,1,2,3,4,5,6);
var_dump(searchincircularsorterlist($array,sizeof($array),4));