вопрос о условии, если в двоичном поиске

Question

int binary_search(const vector<int>& matrix, int target) {

        int start = 0, end = matrix.size() - 1; 
        while (start < end) {
            int mid = start + (end - start)/2;
            if (matrix[mid] <= target) {  // if (matrix[mid] < target)
                start = mid + 1;
            } else {
                end = mid;
            }
        }
        return end;
}
int main()
{
    cout << binary_search({1, 3, 7, 10, 20}, 15);
    return 0;
}

Привет, я не понимаю, в чем разница между «<=» и «<=» в while l oop. </p>

Самая запутанная часть двоичного поиска - я никогда не уверен, какой один использовать «<=» или «<» всякий раз, когда дело доходит до оператора условия: while l oop condition или if. </p>

Даже если у меня есть основная c идея, но когда дело доходит до кодирование, как я могу быть уверен и уверен, что это должно быть «<=», что должно быть «<». </p>

Я ценю, если кто-то может ввести.

Спасибо!

Answer 1

На самом деле,

(1) когда matrix [mid] == target, вы можете напрямую вернуть туда себя.

(2) Если start == end, то вы смотрите только на один элемент (равен ли он цели или нет).

Если он не равен цели, мы говорим, что элемент не найден, иначе элемент найден по определенному индексу

Из вашего кода кажется, что вы предположили, что цель будет присутствовать в матрица, и вы напрямую возвращаетесь "end" без start <= end, что тоже отлично работает. </p>

Итак, если вы не предполагаете, что цель будет в матрице, тогда вы должны поставить условие start <= также конец. </p>