Рубрики

Поиск в массиве строк, где сортируются непустые строки

Дан массив строк. Массив содержит как пустые, так и непустые строки. Все непустые строки расположены в отсортированном порядке. Пустые строки могут присутствовать где угодно между непустыми строками.

Примеры:

Input :  arr[] =  {"for", "", "", "", "geeks", 
                   "ide", "", "practice", "" , 
                   "", "quiz", "", ""};
          str = "quiz"
Output :   10
The string "quiz" is present at index 10 in 
given array.

Простое решение заключается в линейном поиске заданной строки в массиве строк.

Лучшее решение — сделать модифицированный бинарный поиск. Как и при обычном бинарном поиске, мы сравниваем данную строку со средней строкой. Если средняя строка пуста, мы находим ближайшую непустую строку x (путем линейного поиска с обеих сторон). Как только мы находим x, мы делаем стандартный бинарный поиск, т.е. сравниваем данную строку с x. Если str совпадает с x, мы возвращаем индекс x. если str больше, мы повторяем для правой половины, иначе мы повторяем для левой половины.

Ниже приведена реализация идеи.

C ++

// C ++ программа для поиска местоположения строки в
// массив строк, который сортируется и
// между строками есть пустые строки.
#include <bits/stdc++.h>

using namespace std;

  
// Сравнение двух строк равно

int compareStrings(string str1, string str2)

{

    int i = 0;

    while (str1[i] == str2[i] && str1[i] != '\0')

        i++;

    if (str1[i] > str2[i])

        return -1;

  

    return (str1[i] < str2[i]);

}

  
// Основная функция для поиска местоположения строки

int searchStr(string arr[], string str, int first,

                                        int last)

{

    if (first > last)

        return -1;

  

    // Переместиться с середины на середину

    int mid = (last+first)/2;

  

    // Если середина пуста, найти непустую строку в шкафу

    if (arr[mid].empty())

    {

        // Если середина пуста, поиск по обе стороны от середины

        // и найти ближайшую непустую строку, и

        // установить середину соответственно.

        int left  = mid - 1;

        int right = mid + 1;

        while (true)

        {

            if (left < first && right > last)

                return -1;

            if (right<=last && !arr[right].empty())

            {

                mid = right;

                break;

            }

            if (left>=first && !arr[left].empty())

            {

                mid = left;

                break;

            }

            right++;

            left--;

        }

    }

  

    // Если str найден в середине

    if (compareStrings(str, arr[mid]) == 0)

        return mid;

  

    // Если str больше середины

    if (compareStrings(str, arr[mid]) < 0)

        return searchStr(arr, str, mid+1, last);

  

    // Если str меньше среднего

    return searchStr(arr, str, first, mid-1);

}

  
// Код драйвера

int main()

{

    // Входная строка строк.

    string arr[] = {"for", "", "", "", "geeks", "ide", "",

                     "practice", "" , "", "quiz", "", ""};

  

    // ввод строки поиска

    string str = "quiz";

    int n = sizeof(arr)/sizeof(arr[0]);

  

    cout << searchStr(arr, str, 0, n-1);

    return 0;

}

Джава

// Java-программа для поиска местоположения str в
// массив строк, который сортируется и
// между строками есть пустые строки.

import java.util.*;

  

class GFG 

{

  

    // Сравнение двух строк равно

    static int compareStrings(String str1, 

                              String str2)

    {

        int i = 0;

        while (i < str1.length() - 1 && 

                   str1.charAt(i) == str2.charAt(i))

            i++;

  

        if (str1.charAt(i) > str2.charAt(i))

            return -1;

  

        if (str1.charAt(i) < str2.charAt(i))

            return 1;

        else

            return 0;

    }

  

    // Основная функция для поиска местоположения строки

    static int searchStr(String[] arr, String str, 

                            int first, int last) 

    {

        if (first > last)

            return -1;

  

        // Переместиться с середины на середину

        int mid = (last + first) / 2;

  

        // Если середина пуста,

        // найти непустую строку шкафа

        if (arr[mid].isEmpty())

        {

  

            // Если середина пуста, поиск по обе стороны от середины

            // и найти ближайшую непустую строку, и

            // установить середину соответственно.

            int left = mid - 1;

            int right = mid + 1;

            while (true)

            {

                if (left < right && right > last)

                    return -1;

                if (right <= last && !arr[right].isEmpty()) 

                {

                    mid = right;

                    break;

                }

                if (left >= right && !arr[left].isEmpty()) 

                {

                    mid = left;

                    break;

                }

                right++;

                left--;

            }

        }

  

        // Если str найден в середине

        if (compareStrings(str, arr[mid]) == 0)

            return mid;

  

        // Если str больше середины

        if (compareStrings(str, arr[mid]) < 0)

            return searchStr(arr, str, mid + 1, last);

  

        // Если str меньше среднего

        return searchStr(arr, str, first, mid - 1);

    }

  

    // Код драйвера

    public static void main(String[] args)

    {

  

        // Входная строка строк.

        String[] arr = { "for", "", "", "", "geeks"

                         "ide", "", "practice", ""

                         "", "quiz", "", "" };

  

        // ввод строки поиска

        String str = "quiz";

        int n = arr.length;

  

        System.out.println(searchStr(arr, str, 0, n - 1));

    }

}

  
// Этот код предоставлен
// sanjeev2552

python3

# Python3 программа для поиска местоположения
# str в массиве строк, который отсортирован
# и содержит пустые строки между строками.

  
# Сравнение двух строк равно

def compareStrings(str1, str2): 

   

    i = 0 

    while i < len(str1) - 1 and str1[i] == str2[i]: 

        i += 1 

    if str1[i] > str2[i]: 

        return -1 

  

    return str1[i] < str2[i]

   
# Основная функция для поиска местоположения строки

def searchStr(arr, string, first, last): 

   

    if first > last:

        return -1 

  

    # Переместиться с середины на середину

    mid = (last + first) // 2 

  

    # Если середина пуста, найти непустую строку в шкафу

    if len(arr[mid]) == 0

       

        # Если середина пуста, поиск по обе стороны от середины

        # и найти ближайшую непустую строку, и

        # установить середину соответственно.

        left, right = mid - 1, mid + 1 

        while True

           

            if left < first and right > last: 

                return -1

                  

            if right <= last and len(arr[right]) != 0

                mid = right 

                break 

               

            if left >= first and len(arr[left]) != 0

                mid = left 

                break 

               

            right += 1 

            left -= 1

  

    # Если str найден в середине

    if compareStrings(string, arr[mid]) == 0

        return mid 

  

    # Если str больше середины

    if compareStrings(string, arr[mid]) < 0

        return searchStr(arr, string, mid+1, last) 

  

    # Если str меньше среднего

    return searchStr(arr, string, first, mid-1

   
Код водителя

if __name__ == "__main__"

   

    # Входная строка строк.

    arr = ["for", "", "", "", "geeks", "ide", "", 

                    "practice", "" , "", "quiz", "", ""] 

  

    # input Строка поиска

    string = "quiz" 

    n = len(arr) 

  

    print(searchStr(arr, string, 0, n-1)) 

      
# Этот код предоставлен Rituraj Jain

Выход:

  10

Хотя этот подход работает лучше, чем линейный поиск, наихудший вариант выполнения этого алгоритма — O (n).

Эта статья предоставлена г-ном Сомешем Авастхи . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Поиск в массиве строк, где сортируются непустые строки

0.00 (0%) 0 votes