Dada una array de strings. La array tiene strings vacías y no vacías. Todas las strings no vacías están ordenadas. Las strings vacías pueden estar presentes en cualquier lugar entre strings no vacías.
Ejemplos:
Input : arr[] = {"for", "", "", "", "geeks",
"ide", "", "practice", "" ,
"", "quiz", "", ""};
str = "quiz"
Output : 10
The string "quiz" is present at index 10 in
given array.
Una solución simple es buscar linealmente una string dada en una array de strings.
Una mejor solución es hacer una búsqueda binaria modificada. Al igual que la búsqueda binaria normal, comparamos la string dada con la string del medio. Si la string central está vacía, encontramos la string x no vacía más cercana (buscando linealmente en ambos lados). Una vez que encontramos x, hacemos una búsqueda binaria estándar, es decir, comparamos la string dada con x. Si str es lo mismo que x, devolvemos el índice de x. si str es mayor, recurrimos para la mitad derecha, de lo contrario recurrimos para la mitad izquierda.
A continuación se muestra la implementación de la idea:
C++
// C++ program to find location of a str in
// an array of strings which is sorted and
// has empty strings between strings.
#include <bits/stdc++.h>
using namespace std;
// Compare two string equals are not
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]);
}
// Main function to find string location
int searchStr(string arr[], string str, int first,
int last)
{
if (first > last)
return -1;
// Move mid to the middle
int mid = (last+first)/2;
// If mid is empty , find closest non-empty string
if (arr[mid].empty())
{
// If mid is empty, search in both sides of mid
// and find the closest non-empty string, and
// set mid accordingly.
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--;
}
}
// If str is found at mid
if (compareStrings(str, arr[mid]) == 0)
return mid;
// If str is greater than mid
if (compareStrings(str, arr[mid]) < 0)
return searchStr(arr, str, mid+1, last);
// If str is smaller than mid
return searchStr(arr, str, first, mid-1);
}
// Driver Code
int main()
{
// Input arr of Strings.
string arr[] = {"for", "", "", "", "geeks", "ide", "",
"practice", "" , "", "quiz", "", ""};
// input Search String
string str = "quiz";
int n = sizeof(arr)/sizeof(arr[0]);
cout << searchStr(arr, str, 0, n-1);
return 0;
}
Java
// Java program to find location of a str in
// an array of strings which is sorted and
// has empty strings between strings.
import java.util.*;
class GFG
{
// Compare two string equals are not
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;
}
// Main function to find string location
static int searchStr(String[] arr, String str,
int first, int last)
{
if (first > last)
return -1;
// Move mid to the middle
int mid = (last + first) / 2;
// If mid is empty,
// find closest non-empty string
if (arr[mid].isEmpty())
{
// If mid is empty, search in both sides of mid
// and find the closest non-empty string, and
// set mid accordingly.
int left = mid - 1;
int right = mid + 1;
while (true)
{
if (left < first && right > last)
return -1;
if (right <= last && !arr[right].isEmpty())
{
mid = right;
break;
}
if (left >= first && !arr[left].isEmpty())
{
mid = left;
break;
}
right++;
left--;
}
}
// If str is found at mid
if (compareStrings(str, arr[mid]) == 0)
return mid;
// If str is greater than mid
if (compareStrings(str, arr[mid]) < 0)
return searchStr(arr, str, mid + 1, last);
// If str is smaller than mid
return searchStr(arr, str, first, mid - 1);
}
// Driver Code
public static void main(String[] args)
{
// Input arr of Strings.
String[] arr = { "for", "", "", "", "geeks",
"ide", "", "practice", "",
"", "quiz", "", "" };
// input Search String
String str = "quiz";
int n = arr.length;
System.out.println(searchStr(arr, str, 0, n - 1));
}
}
// This code is contributed by
// sanjeev2552
Python3
# Python3 program to find the location of # an str in an array of strings which is sorted # and has empty strings between strings. # Compare two string equals are not 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] # Main function to find string location def searchStr(arr, string, first, last): if first > last: return -1 # Move mid to the middle mid = (last + first) // 2 # If mid is empty , find closest non-empty string if len(arr[mid]) == 0: # If mid is empty, search in both sides of mid # and find the closest non-empty string, and # set mid accordingly. 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 # If str is found at mid if compareStrings(string, arr[mid]) == 0: return mid # If str is greater than mid if compareStrings(string, arr[mid]) < 0: return searchStr(arr, string, mid+1, last) # If str is smaller than mid return searchStr(arr, string, first, mid-1) # Driver Code if __name__ == "__main__": # Input arr of Strings. arr = ["for", "", "", "", "geeks", "ide", "", "practice", "" , "", "quiz", "", ""] # input Search String string = "quiz" n = len(arr) print(searchStr(arr, string, 0, n-1)) # This code is contributed by Rituraj Jain
Javascript
<script>
// Javascript program to find location of a str in
// an array of strings which is sorted and
// has empty strings between strings.
// Compare two string equals are not
function compareStrings(str1, str2)
{
let i = 0;
while (i < str1.length - 1 &&
str1[i] == str2[i])
i++;
if (str1[i] > str2[i])
return -1;
if (str1[i] < str2[i])
return 1;
else
return 0;
}
// Main function to find string location
function searchStr(arr, str, first, last)
{
if (first > last)
return -1;
// Move mid to the middle
let mid = parseInt((last + first) / 2, 10);
// If mid is empty,
// find closest non-empty string
if (arr[mid] == "")
{
// If mid is empty, search in both sides of mid
// and find the closest non-empty string, and
// set mid accordingly.
let left = mid - 1;
let right = mid + 1;
while (true)
{
if (left < right && right > last)
return -1;
if (right <= last && arr[right] != "")
{
mid = right;
break;
}
if (left >= right && !arr[left] == "")
{
mid = left;
break;
}
right++;
left--;
}
}
// If str is found at mid
if (compareStrings(str, arr[mid]) == 0)
return mid;
// If str is greater than mid
if (compareStrings(str, arr[mid]) < 0)
return searchStr(arr, str, mid + 1, last);
// If str is smaller than mid
return searchStr(arr, str, first, mid - 1);
}
// Input arr of Strings.
let arr = [ "for", "", "", "", "geeks",
"ide", "", "practice", "",
"", "quiz", "", "" ];
// input Search String
let str = "quiz";
let n = arr.length;
document.write(searchStr(arr, str, 0, n - 1));
// This code is contributed by vaibhavrabadiya3.
</script>
Producción:
10
El uso de la búsqueda lineal nos llevaría a O(L*N), donde L es la comparación de strings. Para optimizar el tiempo de ejecución, utilizamos la búsqueda binaria haciendo que la complejidad del tiempo sea O(L(logN)).
Este artículo es una contribución del Sr. Somesh Awasthi . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA