Найти первый элемент в отсортированном массиве, который больше целевого

Ответ 1

Особенно элегантный способ думать об этой проблеме - подумать о выполнении двоичного поиска по преобразованной версии массива, где массив был изменен с помощью функции

f(x) = 1 if x > target
       0 else

Теперь цель состоит в том, чтобы найти первое место, где эта функция принимает значение 1. Мы можем сделать это, используя двоичный поиск следующим образом:

int low = 0, high = numElems; // numElems is the size of the array i.e arr.size() 
while (low != high) {
    int mid = (low + high) / 2; // Or a fancy way to avoid int overflow
    if (arr[mid] <= target) {
        /* This index, and everything below it, must not be the first element
         * greater than what we're looking for because this element is no greater
         * than the element.
         */
        low = mid + 1;
    }
    else {
        /* This element is at least as large as the element, so anything after it can't
         * be the first element that at least as large.
         */
        high = mid;
    }
}
/* Now, low and high both point to the element in question. */

Чтобы убедиться, что этот алгоритм правильный, рассмотрите каждое сравнение. Если мы найдем элемент, который не больше целевого элемента, то он и все под ним не могут совпадать, поэтому нет необходимости искать этот регион. Мы можем рекурсивно искать правильную половину. Если мы найдем элемент, который больше, чем этот элемент, то все, что после него также должно быть больше, поэтому они не могут быть элементом first, который больше, и поэтому нам не нужно искать их. Таким образом, средний элемент - это последнее возможное место.

Обратите внимание, что на каждой итерации мы отбрасываем по крайней мере половину оставшихся элементов из рассмотрения. Если верхняя ветвь выполняется, то элементы в диапазоне [low, (low + high)/2] отбрасываются, что приводит к потере пола ((низкий + высокий)/2) - низкий + 1 >= (низкий + высокий)/2 - низкий = (высокий - низкий)/2 элемента.

Если нижняя ветвь выполняется, то элементы в диапазоне [(низкий + высокий)/2 + 1, высокий] все отбрасываются. Это лишает нас высокопольных (низкий + высокий)/2 + 1 >= высокий - (низкий + высокий)/2 = (высокий - низкий)/2 элемента.

Следовательно, мы закончим поиск первого элемента, большего, чем цель в O (lg n) итерациях этого процесса.

EDIT: Здесь трассировка алгоритма, работающего на массиве 0 0 1 1 1 1.

Вначале мы имеем

0 0 1 1 1 1
L = 0       H = 6

Итак, мы вычисляем mid = (0 + 6)/2 = 3, поэтому мы проверяем элемент в позиции 3, который имеет значение 1. Так как 1 > 0, положим high = mid = 3. Теперь мы имеем

0 0 1
L     H

Мы вычисляем mid = (0 + 3)/2 = 1, поэтому мы проверяем элемент 1. Так как это имеет значение 0 <= 0, мы устанавливаем mid = low + 1 = 2. Теперь мы остаемся с L = 2 и H = 3:

0 0 1
    L H

Теперь мы вычисляем mid = (2 + 3)/2 = 2. Элемент с индексом 2 равен 1, а так как 1 & ge; 0, положим H = mid = 2, и в этот момент мы остановимся, и действительно, мы смотрим на первый элемент, превышающий 0.

Надеюсь, это поможет!

Ответ 2

Вы можете использовать std::upper_bound, если массив отсортирован (предполагается, что n - размер массива a[]):

int* p = std::upper_bound( a, a + n, x );
if( p == a + n )
     std::cout << "No element greater";
else
     std::cout << "The first element greater is " << *p
               << " at position " << p - a;

Ответ 3

Как насчет следующего рекурсивного подхода:

    public static int minElementGreaterThanOrEqualToKey(int A[], int key,
        int imin, int imax) {

    // Return -1 if the maximum value is less than the minimum or if the key
    // is great than the maximum
    if (imax < imin || key > A[imax])
        return -1;

    // Return the first element of the array if that element is greater than
    // or equal to the key.
    if (key < A[imin])
        return imin;

    // When the minimum and maximum values become equal, we have located the element. 
    if (imax == imin)
        return imax;

    else {
        // calculate midpoint to cut set in half, avoiding integer overflow
        int imid = imin + ((imax - imin) / 2);

        // if key is in upper subset, then recursively search in that subset
        if (A[imid] < key)
            return minElementGreaterThanOrEqualToKey(A, key, imid + 1, imax);

        // if key is in lower subset, then recursively search in that subset
        else
            return minElementGreaterThanOrEqualToKey(A, key, imin, imid);
    }
}

Ответ 4

В моей следующей реализации используется условие bottom <= top, которое отличается от ответа @templatetypedef.

int FirstElementGreaterThan(int n, const vector<int>& values) {
  int B = 0, T = values.size() - 1, M = 0;
  while (B <= T) { // B strictly increases, T strictly decreases
    M = B + (T - B) / 2;
    if (values[M] <= n) { // all values at or before M are not the target
      B = M + 1;
    } else {
      T = M - 1;// search for other elements before M
    }
  }
  return T + 1;
}

Ответ 5

здесь приведен модифицированный код двоичного поиска в JAVA со сложностью времени O (logn), который:

• возвращает индекс элемента для поиска , если элемент присутствует
• возвращает индекс следующего большего элемента, если искомый элемент отсутствует в массиве
• возвращает -1, если выполняется поиск элемента, большего, чем наибольший элемент массива

public static int search(int arr[],int key) {
    int low=0,high=arr.length,mid=-1;
    boolean flag=false;

    while(low<high) {
        mid=(low+high)/2;
        if(arr[mid]==key) {
            flag=true;
            break;
        } else if(arr[mid]<key) {
            low=mid+1;
        } else {
            high=mid;
        }
    }
    if(flag) {
        return mid;
    }
    else {
        if(low>=arr.length)
            return -1;
        else
        return low;
        //high will give next smaller
    }
}

public static void main(String args[]) throws IOException {
    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    //int n=Integer.parseInt(br.readLine());
    int arr[]={12,15,54,221,712};
    int key=71;
    System.out.println(search(arr,key));
    br.close();
}

Ответ 6

kind = 0: точное совпадение, kind = 1: чуть больше x, kind = -1: чуть меньше x;

Возвращает -1, если совпадений не найдено.

#include <iostream>
#include <algorithm>

using namespace std;


int g(int arr[], int l , int r, int x, int kind){
    switch(kind){
    case 0: // for exact match
        if(arr[l] == x) return l;
        else if(arr[r] == x) return r;
        else return -1;
        break;
    case 1: // for just greater than x
        if(arr[l]>=x) return l;
        else if(arr[r]>=x) return r;
        else return -1;
        break;
    case -1: // for just smaller than x
        if(arr[r]<=x) return r;
        else if(arr[l] <= x) return l;
        else return -1;
        break;
    default:
        cout <<"please give "kind" as 0, -1, 1 only" << ednl;
    }
}

int f(int arr[], int n, int l, int r, int x, int kind){
    if(l==r) return l;
    if(l>r) return -1;
    int m = l+(r-l)/2;
    while(m>l){
        if(arr[m] == x) return m;
        if(arr[m] > x) r = m;
        if(arr[m] < x) l = m;
        m = l+(r-l)/2;
    }
    int pos = g(arr, l, r, x, kind);
    return pos;
}

int main()
{
    int arr[] = {1,2,3,5,8,14, 22, 44, 55};
    int n = sizeof(arr)/sizeof(arr[0]);
    sort(arr, arr+n);
    int tcs;
    cin >> tcs;
    while(tcs--){
        int l = 0, r = n-1, x = 88, kind = -1; // you can modify these values
        cin >> x;
        int pos = f(arr, n, l, r, x, kind);
        // kind =0: exact match, kind=1: just grater than x, kind=-1: just smaller than x;
        cout <<"position"<< pos << " Value ";
        if(pos >= 0) cout << arr[pos];
        cout << endl;
    }
    return 0;
}

Ответ 7

После многих лет обучения алгоритмам мой подход к решению задач бинарного поиска состоит в установке начала и конца элементов, а не вне массива. Таким образом, я чувствую, что происходит, и все под контролем, не чувствуя волшебства по поводу решения.

Ключевым моментом в решении задач бинарного поиска (и многих других решений, основанных на циклах) является набор хороших инвариантов. Выбор правильного инварианта делает задачу решения тортом. Мне потребовалось много лет, чтобы понять инвариантную концепцию, хотя я изучил ее впервые в колледже много лет назад.

Даже если вы хотите решить проблемы бинарного поиска, выбрав начало или конец вне массива, вы все равно можете достичь этого с помощью соответствующего инварианта. При этом, мой выбор указан выше, чтобы всегда устанавливать начало в первом элементе и конец в последнем элементе массива.

Итак, подведем итоги, пока что имеем:

int start = 0; 
int end = a.length - 1; 

Теперь инвариант. Массив прямо сейчас у нас есть [начало, конец]. Мы еще ничего не знаем об элементах. Все они могут быть больше цели, или все могут быть меньше, или некоторые меньше, а некоторые больше. Поэтому мы пока не можем делать никаких предположений об элементах. Наша цель - найти первый элемент больше цели. Таким образом, мы выбираем инварианты как это:

Любой элемент справа от конца больше цели.
Любой элемент слева от начала меньше или равен цели.

Мы можем легко увидеть, что наш инвариант является правильным в начале (то есть перед тем, как войти в любой цикл). Все элементы слева от начала (без элементов в основном) меньше или равны цели, то же самое для конца.

С этим инвариантом, когда цикл завершится, ответом будет первый элемент после конца (помните, инвариант, что все правые стороны конца больше цели?). Так что answer = end + 1.

Также нужно отметить, что когда цикл завершится, начало будет на единицу больше конца. то есть start = end + 1. Таким образом, мы также можем сказать, что start также является ответом (инвариантным было то, что что-либо слева от начала меньше или равно цели, поэтому сам start является первым элементом больше цели).

Так что, как говорится, вот код. Вы должны чувствовать себя комфортно в каждой строке этого кода, и вы не должны чувствовать никакой магии вообще. Если нет, пожалуйста, прокомментируйте, в чем двусмысленность, и я буду более чем рад ответить.

public static int find(int a[], int target) {
    int st = 0; 
    int end = a.length - 1; 
    while(st <= end) {
        int mid = (st + end) / 2;   // or elegant way of st + (end - st) / 2; 
        if (a[mid] <= target) {
            st = mid + 1; 
        } else { // mid > target
            end = mid - 1; 
        }
    }
    return st; // or return end + 1
}

Несколько дополнительных замечаний об этом способе решения проблем бинарного поиска:

Этот тип решения всегда уменьшает размер подмассивов по крайней мере на 1. Это очевидно в коде. Новое начало или конец - либо +1, либо -1 середина. Мне нравится этот подход лучше, чем включение середины в обе стороны или в одну сторону, а потом рассуждать, почему алгоритм верен. Таким образом, это более ощутимо и более безошибочно.

Условием для цикла while является st <= end. Не st < end. Это означает, что наименьший размер, который входит в цикл while, - это массив размера 1. И это полностью соответствует тому, что мы ожидаем. В других способах решения проблем бинарного поиска иногда наименьший размер - это массив размера 2 (если st <end), и, честно говоря, мне гораздо проще всегда обращаться ко всем размерам массива, включая размер 1.

Поэтому надеюсь, что это проясняет решение этой проблемы и многих других проблем бинарного поиска. Относитесь к этому решению как к способу профессионального понимания и решения многих других проблем бинарного поиска, не колебаясь, работает ли алгоритм для граничных случаев или нет.