Dada una array ordenada de strings y una string x, encuentre un índice de x si está presente en la array.
Ejemplos:
Input : arr[] = {"contribute", "geeks", "ide", "practice"}, x = "ide"
Output : 2
The String x is present at index 2.
Input : arr[] = {"contribute", "geeks", "ide", "practice"}, x = "zz"
Output : -1
The String "zz" is not present.
Prerrequisitos: búsqueda binaria , comparación de strings en Java
La idea es comparar x con la string del medio en la array dada. Si coincide, devuelva mid, de lo contrario, si es más pequeño que mid, busque en la mitad izquierda, de lo contrario busque en la mitad derecha.
C++
// CPP program to implement Binary Search for strings
#include<bits/stdc++.h>
using namespace std;
// Returns index of x if it is present in arr[],
// else return -1
int binarySearch(string arr[], string x,int n)
{
int l = 0 ;
int r = n - 1;
while (l <= r)
{
int m = l + (r - l) / 2;
int res = -1000; //some random value assigned because if res is already 0 then
//it will always return 0
if (x == (arr[m]))
res = 0;
// Check if x is present at mid
if (res == 0)
return m;
// If x greater, ignore left half
if (x > (arr[m]))
l = m + 1;
// If x is smaller, ignore right half
else
r = m - 1;
}
return -1;
}
// Driver code
int main()
{
string arr[] = { "contribute", "geeks", "ide", "practice"};
string x = "ide";
int n = 4;
int result = binarySearch(arr, x,n);
if (result == -1)
cout << ("Element not present");
else
cout << ("Element found at index ") << result;
}
// This code is contributed by
// Shashank_Sharma
Java
// Java program to implement Binary Search for strings
class GFG {
// Returns index of x if it is present in arr[],
// else return -1
static int binarySearch(String[] arr, String x)
{
int l = 0, r = arr.length - 1;
while (l <= r) {
int m = l + (r - l) / 2;
int res = x.compareTo(arr[m]);
// Check if x is present at mid
if (res == 0)
return m;
// If x greater, ignore left half
if (res > 0)
l = m + 1;
// If x is smaller, ignore right half
else
r = m - 1;
}
return -1;
}
// Driver method to test above
public static void main(String []args)
{
String[] arr = { "contribute", "geeks", "ide", "practice"};
String x = "ide";
int result = binarySearch(arr, x);
if (result == -1)
System.out.println("Element not present");
else
System.out.println("Element found at "
+ "index " + result);
}
}
Python3
# Python3 program to implement Binary
# Search for strings
# Returns index of x if it is present
# in arr[], else return -1
def binarySearch(arr, x):
l = 0
r = len(arr)
while (l <= r):
m = l + ((r - l) // 2)
res = (x == arr[m])
# Check if x is present at mid
if (res == 0):
return m - 1
# If x greater, ignore left half
if (res > 0):
l = m + 1
# If x is smaller, ignore right half
else:
r = m - 1
return -1
# Driver Code
if __name__ == "__main__":
arr = ["contribute", "geeks",
"ide", "practice"];
x = "ide"
result = binarySearch(arr, x)
if (result == -1):
print("Element not present")
else:
print("Element found at index" ,
result)
# This code is contributed by ita_c
C#
// C# program to implement Binary Search for strings
using System;
class GFG {
// Returns index of x if it is present in arr[],
// else return -1
static int binarySearch(String[] arr, String x)
{
int l = 0, r = arr.Length - 1;
while (l <= r) {
int m = l + (r - l) / 2;
int res = x.CompareTo(arr[m]);
// Check if x is present at mid
if (res == 0)
return m;
// If x greater, ignore left half
if (res > 0)
l = m + 1;
// If x is smaller, ignore right half
else
r = m - 1;
}
return -1;
}
// Driver method to test above
public static void Main(String []args)
{
String[] arr = { "contribute", "geeks", "ide", "practice"};
String x = "ide";
int result = binarySearch(arr, x);
if (result == -1)
Console.WriteLine("Element not present");
else
Console.WriteLine("Element found at "
+ "index " + result);
}
// This code is contributed by Ryuga
}
PHP
<?php
// PHP program to implement Binary
// Search for strings
// Returns index of x if it is present
// in arr[], else return -1
function binarySearch($arr, $x)
{
$l = 0;
$r = count($arr);
while ($l <= $r)
{
$m = $l + (int)(($r - $l) / 2);
$res = strcmp($x, $arr[$m]);
// Check if x is present at mid
if ($res == 0)
return $m - 1;
// If x greater, ignore left half
if ($res > 0)
$l = $m + 1;
// If x is smaller, ignore right half
else
$r = $m - 1;
}
return -1;
}
// Driver Code
$arr = array("contribute", "geeks",
"ide", "practice");
$x = "ide";
$result = binarySearch($arr, $x);
if ($result == -1)
print("Element not present");
else
print("Element found at index " .
$result);
// This code is contributed by mits
?>
Javascript
<script>
// Javascript program to implement Binary Search for strings
// Returns index of x if it is present in arr[],
// else return -1
function binarySearch(arr,x)
{
let l = 0, r = arr.length - 1;
while (l <= r) {
let m = l + Math.floor((r - l) / 2);
let res = x.localeCompare(arr[m]);
// Check if x is present at mid
if (res == 0)
return m;
// If x greater, ignore left half
if (res > 0)
l = m + 1;
// If x is smaller, ignore right half
else
r = m - 1;
}
return -1;
}
// Driver method to test above
let arr=["contribute", "geeks", "ide", "practice"];
let x = "ide";
let result = binarySearch(arr, x);
if (result == -1)
document.write("Element not present<br>");
else
document.write("Element found at "
+ "index " + result+"<br>");
// This code is contributed by rag2127
</script>
Producción:
Element found at index 2
Publicación traducida automáticamente
Artículo escrito por SamuelAntwi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA