La búsqueda binaria es muy fácil, ¿verdad? Bueno, la búsqueda binaria puede volverse compleja cuando ocurre la duplicación de elementos en la lista ordenada de valores. No siempre es el «contiene o no» lo que buscamos usando la búsqueda binaria, pero hay 5 variantes como las siguientes:
1) Contiene (Verdadero o Falso)
2) Índice de la primera aparición de una clave
3) Índice de la última aparición de una clave
4) Índice del elemento menor mayor que la clave
5) Índice del elemento mayor menor que la clave
Cada una de estas búsquedas, si bien la lógica base sigue siendo la misma, tiene una pequeña variación en la implementación y los programadores de la competencia deben conocerlas. Es posible que haya visto otros enfoques como este para encontrar la primera y la última ocurrencia, donde compara el elemento adyacente también para verificar que se alcanza el primer/último elemento.
Desde una perspectiva de complejidad, puede parecer un algoritmo O(log n), pero no funciona cuando las comparaciones en sí son caras. Un problema para probar este punto está vinculado al final de esta publicación, siéntase libre de probarlo.
Variante 1: Contiene clave (Verdadero o Falso)
Input : 2 3 3 5 5 5 6 6 Function : Contains(4) Returns : False Function : Contains(5) Returns : True
Variante 2: Primera aparición de clave (índice de array). Esto es similar a
C++
std::lower_bound(...)
Input : 2 3 3 5 5 5 6 6 Function : first(3) Returns : 1 Function : first(5) Returns : 3 Function : first(4) Returns : -1
Variante 3: última aparición de clave (índice de array)
Input : 2 3 3 5 5 5 6 6 Function : last(3) Returns : 2 Function : last(5) Returns : 5 Function : last(4) Returns : -1
Variante 4: índice (primera ocurrencia) del menor entero mayor que la clave. Esto es similar a
C++
std::upper_bound(...)
Input : 2 3 3 5 5 5 6 6 Function : leastGreater(2) Returns : 1 Function : leastGreater(5) Returns : 6
Variante 5: índice (última aparición) del mayor entero menor que la clave
Input : 2 3 3 5 5 5 6 6 Function : greatestLesser(2) Returns : -1 Function : greatestLesser(5) Returns : 2
Como verá a continuación, si observa la clara diferencia entre las implementaciones, verá que se utiliza la misma lógica para encontrar diferentes variantes de búsqueda binaria.
C++
// C++ program to variants of Binary Search
#include <bits/stdc++.h>
using namespace std;
int n = 8; // array size
int a[] = { 2, 3, 3, 5, 5, 5, 6, 6 }; // Sorted array
/* Find if key is in array
* Returns: True if key belongs to array,
* False if key doesn't belong to array */
bool contains(int low, int high, int key)
{
bool ans = false;
while (low <= high) {
int mid = low + (high - low) / 2;
int midVal = a[mid];
if (midVal < key) {
// if mid is less than key, all elements
// in range [low, mid] are also less
// so we now search in [mid + 1, high]
low = mid + 1;
}
else if (midVal > key) {
// if mid is greater than key, all elements
// in range [mid + 1, high] are also greater
// so we now search in [low, mid - 1]
high = mid - 1;
}
else if (midVal == key) {
// comparison added just for the sake
// of clarity if mid is equal to key, we
// have found that key exists in array
ans = true;
break;
}
}
return ans;
}
/* Find first occurrence index of key in array
* Returns: an index in range [0, n-1] if key belongs
* to array, -1 if key doesn't belong to array
*/
int first(int low, int high, int key)
{
int ans = -1;
while (low <= high) {
int mid = low + (high - low + 1) / 2;
int midVal = a[mid];
if (midVal < key) {
// if mid is less than key, all elements
// in range [low, mid] are also less
// so we now search in [mid + 1, high]
low = mid + 1;
}
else if (midVal > key) {
// if mid is greater than key, all elements
// in range [mid + 1, high] are also greater
// so we now search in [low, mid - 1]
high = mid - 1;
}
else if (midVal == key) {
// if mid is equal to key, we note down
// the last found index then we search
// for more in left side of mid
// so we now search in [low, mid - 1]
ans = mid;
high = mid - 1;
}
}
return ans;
}
/* Find last occurrence index of key in array
* Returns: an index in range [0, n-1] if key
belongs to array,
* -1 if key doesn't belong to array
*/
int last(int low, int high, int key)
{
int ans = -1;
while (low <= high) {
int mid = low + (high - low + 1) / 2;
int midVal = a[mid];
if (midVal < key) {
// if mid is less than key, then all elements
// in range [low, mid - 1] are also less
// so we now search in [mid + 1, high]
low = mid + 1;
}
else if (midVal > key) {
// if mid is greater than key, then all
// elements in range [mid + 1, high] are
// also greater so we now search in
// [low, mid - 1]
high = mid - 1;
}
else if (midVal == key) {
// if mid is equal to key, we note down
// the last found index then we search
// for more in right side of mid
// so we now search in [mid + 1, high]
ans = mid;
low = mid + 1;
}
}
return ans;
}
/* Find index of first occurrence of least element
greater than key in array
* Returns: an index in range [0, n-1] if key is not
the greatest element in array,
* -1 if key is the greatest element in array */
int leastgreater(int low, int high, int key)
{
int ans = -1;
while (low <= high) {
int mid = low + (high - low + 1) / 2;
int midVal = a[mid];
if (midVal < key) {
// if mid is less than key, all elements
// in range [low, mid - 1] are <= key
// then we search in right side of mid
// so we now search in [mid + 1, high]
low = mid + 1;
}
else if (midVal > key) {
// if mid is greater than key, all elements
// in range [mid + 1, high] are >= key
// we note down the last found index, then
// we search in left side of mid
// so we now search in [low, mid - 1]
ans = mid;
high = mid - 1;
}
else if (midVal == key) {
// if mid is equal to key, all elements in
// range [low, mid] are <= key
// so we now search in [mid + 1, high]
low = mid + 1;
}
}
return ans;
}
/* Find index of last occurrence of greatest element
less than key in array
* Returns: an index in range [0, n-1] if key is not
the least element in array,
* -1 if key is the least element in array */
int greatestlesser(int low, int high, int key)
{
int ans = -1;
while (low <= high) {
int mid = low + (high - low + 1) / 2;
int midVal = a[mid];
if (midVal < key) {
// if mid is less than key, all elements
// in range [low, mid - 1] are < key
// we note down the last found index, then
// we search in right side of mid
// so we now search in [mid + 1, high]
ans = mid;
low = mid + 1;
}
else if (midVal > key) {
// if mid is greater than key, all elements
// in range [mid + 1, high] are > key
// then we search in left side of mid
// so we now search in [low, mid - 1]
high = mid - 1;
}
else if (midVal == key) {
// if mid is equal to key, all elements
// in range [mid + 1, high] are >= key
// then we search in left side of mid
// so we now search in [low, mid - 1]
high = mid - 1;
}
}
return ans;
}
int main()
{
printf("Contains\n");
for (int i = 0; i < 10; i++)
printf("%d %d\n", i, contains(0, n - 1, i));
printf("First occurrence of key\n");
for (int i = 0; i < 10; i++)
printf("%d %d\n", i, first(0, n - 1, i));
printf("Last occurrence of key\n");
for (int i = 0; i < 10; i++)
printf("%d %d\n", i, last(0, n - 1, i));
printf("Least integer greater than key\n");
for (int i = 0; i < 10; i++)
printf("%d %d\n", i, leastgreater(0, n - 1, i));
printf("Greatest integer lesser than key\n");
for (int i = 0; i < 10; i++)
printf("%d %d\n", i, greatestlesser(0, n - 1, i));
return 0;
}
Java
// Java program to variants of Binary Search
import java.util.*;
class GFG{
// Array size
static int n = 8;
// Sorted array
static int a[] = { 2, 3, 3, 5, 5, 5, 6, 6 };
/* Find if key is in array
* Returns: True if key belongs to array,
* False if key doesn't belong to array */
static int contains(int low, int high, int key)
{
int ans = 0;
while (low <= high)
{
int mid = low + (high - low) / 2;
int midVal = a[mid];
if (midVal < key)
{
// If mid is less than key, all elements
// in range [low, mid] are also less
// so we now search in [mid + 1, high]
low = mid + 1;
}
else if (midVal > key)
{
// If mid is greater than key, all elements
// in range [mid + 1, high] are also greater
// so we now search in [low, mid - 1]
high = mid - 1;
}
else if (midVal == key)
{
// Comparison added just for the sake
// of clarity if mid is equal to key, we
// have found that key exists in array
ans = 1;
break;
}
}
return ans;
}
/* Find first occurrence index of key in array
* Returns: an index in range [0, n-1] if key belongs
* to array, -1 if key doesn't belong to array
*/
static int first(int low, int high, int key)
{
int ans = -1;
while (low <= high)
{
int mid = low + (high - low + 1) / 2;
int midVal = a[mid];
if (midVal < key)
{
// If mid is less than key, all elements
// in range [low, mid] are also less
// so we now search in [mid + 1, high]
low = mid + 1;
}
else if (midVal > key)
{
// If mid is greater than key, all elements
// in range [mid + 1, high] are also greater
// so we now search in [low, mid - 1]
high = mid - 1;
}
else if (midVal == key)
{
// If mid is equal to key, we note down
// the last found index then we search
// for more in left side of mid
// so we now search in [low, mid - 1]
ans = mid;
high = mid - 1;
}
}
return ans;
}
/* Find last occurrence index of key in array
* Returns: an index in range [0, n-1] if key
belongs to array, -1 if key doesn't
belong to array
*/
static int last(int low, int high, int key)
{
int ans = -1;
while (low <= high)
{
int mid = low + (high - low + 1) / 2;
int midVal = a[mid];
if (midVal < key)
{
// If mid is less than key, then all elements
// in range [low, mid - 1] are also less
// so we now search in [mid + 1, high]
low = mid + 1;
}
else if (midVal > key)
{
// If mid is greater than key, then all
// elements in range [mid + 1, high] are
// also greater so we now search in
// [low, mid - 1]
high = mid - 1;
}
else if (midVal == key)
{
// If mid is equal to key, we note down
// the last found index then we search
// for more in right side of mid
// so we now search in [mid + 1, high]
ans = mid;
low = mid + 1;
}
}
return ans;
}
/* Find index of first occurrence of least element
greater than key in array
* Returns: an index in range [0, n-1] if key is not
the greatest element in array, -1 if key
* is the greatest element in array */
static int leastgreater(int low, int high, int key)
{
int ans = -1;
while (low <= high)
{
int mid = low + (high - low + 1) / 2;
int midVal = a[mid];
if (midVal < key)
{
// If mid is less than key, all elements
// in range [low, mid - 1] are <= key
// then we search in right side of mid
// so we now search in [mid + 1, high]
low = mid + 1;
}
else if (midVal > key)
{
// If mid is greater than key, all elements
// in range [mid + 1, high] are >= key
// we note down the last found index, then
// we search in left side of mid
// so we now search in [low, mid - 1]
ans = mid;
high = mid - 1;
}
else if (midVal == key)
{
// If mid is equal to key, all elements in
// range [low, mid] are <= key
// so we now search in [mid + 1, high]
low = mid + 1;
}
}
return ans;
}
/* Find index of last occurrence of greatest element
less than key in array
* Returns: an index in range [0, n-1] if key is not
the least element in array, -1 if
* key is the least element in array */
static int greatestlesser(int low, int high, int key)
{
int ans = -1;
while (low <= high)
{
int mid = low + (high - low + 1) / 2;
int midVal = a[mid];
if (midVal < key)
{
// If mid is less than key, all elements
// in range [low, mid - 1] are < key
// we note down the last found index, then
// we search in right side of mid
// so we now search in [mid + 1, high]
ans = mid;
low = mid + 1;
}
else if (midVal > key)
{
// If mid is greater than key, all elements
// in range [mid + 1, high] are > key
// then we search in left side of mid
// so we now search in [low, mid - 1]
high = mid - 1;
}
else if (midVal == key)
{
// If mid is equal to key, all elements
// in range [mid + 1, high] are >= key
// then we search in left side of mid
// so we now search in [low, mid - 1]
high = mid - 1;
}
}
return ans;
}
// Driver Code
public static void main(String[] args)
{
System.out.println("Contains");
for(int i = 0; i < 10; i++)
System.out.println(i + " " + contains(0, n - 1, i));
System.out.println("First occurrence of key");
for(int i = 0; i < 10; i++)
System.out.println(i + " " + first(0, n - 1, i));
System.out.println("Last occurrence of key");
for(int i = 0; i < 10; i++)
System.out.println(i + " " + last(0, n - 1, i));
System.out.println("Least integer greater than key");
for(int i = 0; i < 10; i++)
System.out.println(i + " " +
leastgreater(0, n - 1, i));
System.out.println("Greatest integer lesser than key");
for(int i = 0; i < 10; i++)
System.out.println(i + " " +
greatestlesser(0, n - 1, i));
}
}
// This code is contributed by divyeshrabadiya07
C#
// C# program to variants of Binary Search
using System;
class GFG{
// Array size
static int n = 8;
// Sorted array
static int[] a = { 2, 3, 3, 5, 5, 5, 6, 6 };
/* Find if key is in array
* Returns: True if key belongs to array,
* False if key doesn't belong to array */
static int contains(int low, int high, int key)
{
int ans = 0;
while (low <= high)
{
int mid = low + (high - low) / 2;
int midVal = a[mid];
if (midVal < key)
{
// If mid is less than key, all elements
// in range [low, mid] are also less
// so we now search in [mid + 1, high]
low = mid + 1;
}
else if (midVal > key)
{
// If mid is greater than key, all elements
// in range [mid + 1, high] are also greater
// so we now search in [low, mid - 1]
high = mid - 1;
}
else if (midVal == key)
{
// Comparison added just for the sake
// of clarity if mid is equal to key, we
// have found that key exists in array
ans = 1;
break;
}
}
return ans;
}
/* Find first occurrence index of key in array
* Returns: an index in range [0, n-1] if key belongs
* to array, -1 if key doesn't belong to array
*/
static int first(int low, int high, int key)
{
int ans = -1;
while (low <= high)
{
int mid = low + (high - low + 1) / 2;
int midVal = a[mid];
if (midVal < key)
{
// If mid is less than key, all elements
// in range [low, mid] are also less
// so we now search in [mid + 1, high]
low = mid + 1;
}
else if (midVal > key)
{
// If mid is greater than key, all elements
// in range [mid + 1, high] are also greater
// so we now search in [low, mid - 1]
high = mid - 1;
}
else if (midVal == key)
{
// If mid is equal to key, we note down
// the last found index then we search
// for more in left side of mid
// so we now search in [low, mid - 1]
ans = mid;
high = mid - 1;
}
}
return ans;
}
/* Find last occurrence index of key in array
* Returns: an index in range [0, n-1] if key
belongs to array, -1 if key doesn't
belong to array
*/
static int last(int low, int high, int key)
{
int ans = -1;
while (low <= high)
{
int mid = low + (high - low + 1) / 2;
int midVal = a[mid];
if (midVal < key)
{
// If mid is less than key, then all elements
// in range [low, mid - 1] are also less
// so we now search in [mid + 1, high]
low = mid + 1;
}
else if (midVal > key)
{
// If mid is greater than key, then all
// elements in range [mid + 1, high] are
// also greater so we now search in
// [low, mid - 1]
high = mid - 1;
}
else if (midVal == key)
{
// If mid is equal to key, we note down
// the last found index then we search
// for more in right side of mid
// so we now search in [mid + 1, high]
ans = mid;
low = mid + 1;
}
}
return ans;
}
/* Find index of first occurrence of least element
greater than key in array
* Returns: an index in range [0, n-1] if key is not
the greatest element in array,
* -1 if key is the greatest element in array */
static int leastgreater(int low, int high, int key)
{
int ans = -1;
while (low <= high)
{
int mid = low + (high - low + 1) / 2;
int midVal = a[mid];
if (midVal < key)
{
// If mid is less than key, all elements
// in range [low, mid - 1] are <= key
// then we search in right side of mid
// so we now search in [mid + 1, high]
low = mid + 1;
}
else if (midVal > key)
{
// If mid is greater than key, all elements
// in range [mid + 1, high] are >= key
// we note down the last found index, then
// we search in left side of mid
// so we now search in [low, mid - 1]
ans = mid;
high = mid - 1;
}
else if (midVal == key)
{
// If mid is equal to key, all elements in
// range [low, mid] are <= key
// so we now search in [mid + 1, high]
low = mid + 1;
}
}
return ans;
}
/* Find index of last occurrence of greatest element
less than key in array
* Returns: an index in range [0, n-1] if key is not
the least element in array,
* -1 if key is the least element in array */
static int greatestlesser(int low, int high, int key)
{
int ans = -1;
while (low <= high)
{
int mid = low + (high - low + 1) / 2;
int midVal = a[mid];
if (midVal < key)
{
// If mid is less than key, all elements
// in range [low, mid - 1] are < key
// we note down the last found index, then
// we search in right side of mid
// so we now search in [mid + 1, high]
ans = mid;
low = mid + 1;
}
else if (midVal > key)
{
// If mid is greater than key, all elements
// in range [mid + 1, high] are > key
// then we search in left side of mid
// so we now search in [low, mid - 1]
high = mid - 1;
}
else if (midVal == key)
{
// If mid is equal to key, all elements
// in range [mid + 1, high] are >= key
// then we search in left side of mid
// so we now search in [low, mid - 1]
high = mid - 1;
}
}
return ans;
}
// Driver Code
static void Main()
{
Console.WriteLine("Contains");
for(int i = 0; i < 10; i++)
Console.WriteLine(i + " " + contains(0, n - 1, i));
Console.WriteLine("First occurrence of key");
for(int i = 0; i < 10; i++)
Console.WriteLine(i + " " + first(0, n - 1, i));
Console.WriteLine("Last occurrence of key");
for(int i = 0; i < 10; i++)
Console.WriteLine(i + " " + last(0, n - 1, i));
Console.WriteLine("Least integer greater than key");
for(int i = 0; i < 10; i++)
Console.WriteLine(i + " " +
leastgreater(0, n - 1, i));
Console.WriteLine("Greatest integer lesser than key");
for(int i = 0; i < 10; i++)
Console.WriteLine(i + " " +
greatestlesser(0, n - 1, i));
}
}
// This code is contributed by divyesh072019
Javascript
// JavaScript program to variants of Binary Search
let n = 8; // array size
let a = [ 2, 3, 3, 5, 5, 5, 6, 6 ]; // Sorted array
/* Find if key is in array
* Returns: True if key belongs to array,
* False if key doesn't belong to array */
function contains(low, high, key)
{
let ans = false;
while (low <= high) {
let mid = low + Math.floor((high - low) / 2);
let midVal = a[mid];
if (midVal < key) {
// if mid is less than key, all elements
// in range [low, mid] are also less
// so we now search in [mid + 1, high]
low = mid + 1;
}
else if (midVal > key) {
// if mid is greater than key, all elements
// in range [mid + 1, high] are also greater
// so we now search in [low, mid - 1]
high = mid - 1;
}
else if (midVal == key) {
// comparison added just for the sake
// of clarity if mid is equal to key, we
// have found that key exists in array
ans = true;
break;
}
}
return ans;
}
/* Find first occurrence index of key in array
* Returns: an index in range [0, n-1] if key belongs
* to array, -1 if key doesn't belong to array
*/
function first(low, high, key)
{
let ans = -1;
while (low <= high) {
let mid = low + Math.floor((high - low + 1) / 2);
let midVal = a[mid];
if (midVal < key) {
// if mid is less than key, all elements
// in range [low, mid] are also less
// so we now search in [mid + 1, high]
low = mid + 1;
}
else if (midVal > key) {
// if mid is greater than key, all elements
// in range [mid + 1, high] are also greater
// so we now search in [low, mid - 1]
high = mid - 1;
}
else if (midVal == key) {
// if mid is equal to key, we note down
// the last found index then we search
// for more in left side of mid
// so we now search in [low, mid - 1]
ans = mid;
high = mid - 1;
}
}
return ans;
}
/* Find last occurrence index of key in array
* Returns: an index in range [0, n-1] if key
belongs to array,
* -1 if key doesn't belong to array
*/
function last(low, high, key)
{
let ans = -1;
while (low <= high) {
let mid = low + Math.floor((high - low + 1) / 2);
let midVal = a[mid];
if (midVal < key) {
// if mid is less than key, then all elements
// in range [low, mid - 1] are also less
// so we now search in [mid + 1, high]
low = mid + 1;
}
else if (midVal > key) {
// if mid is greater than key, then all
// elements in range [mid + 1, high] are
// also greater so we now search in
// [low, mid - 1]
high = mid - 1;
}
else if (midVal == key) {
// if mid is equal to key, we note down
// the last found index then we search
// for more in right side of mid
// so we now search in [mid + 1, high]
ans = mid;
low = mid + 1;
}
}
return ans;
}
/* Find index of first occurrence of least element
greater than key in array
* Returns: an index in range [0, n-1] if key is not
the greatest element in array,
* -1 if key is the greatest element in array */
function leastgreater(low, high, key)
{
let ans = -1;
while (low <= high) {
let mid = low + Math.floor((high - low + 1) / 2);
let midVal = a[mid];
if (midVal < key) {
// if mid is less than key, all elements
// in range [low, mid - 1] are <= key
// then we search in right side of mid
// so we now search in [mid + 1, high]
low = mid + 1;
}
else if (midVal > key) {
// if mid is greater than key, all elements
// in range [mid + 1, high] are >= key
// we note down the last found index, then
// we search in left side of mid
// so we now search in [low, mid - 1]
ans = mid;
high = mid - 1;
}
else if (midVal == key) {
// if mid is equal to key, all elements in
// range [low, mid] are <= key
// so we now search in [mid + 1, high]
low = mid + 1;
}
}
return ans;
}
/* Find index of last occurrence of greatest element
less than key in array
* Returns: an index in range [0, n-1] if key is not
the least element in array,
* -1 if key is the least element in array */
function greatestlesser(low, high, key)
{
let ans = -1;
while (low <= high) {
let mid = low + Math.floor((high - low + 1) / 2);
let midVal = a[mid];
if (midVal < key) {
// if mid is less than key, all elements
// in range [low, mid - 1] are < key
// we note down the last found index, then
// we search in right side of mid
// so we now search in [mid + 1, high]
ans = mid;
low = mid + 1;
}
else if (midVal > key) {
// if mid is greater than key, all elements
// in range [mid + 1, high] are > key
// then we search in left side of mid
// so we now search in [low, mid - 1]
high = mid - 1;
}
else if (midVal == key) {
// if mid is equal to key, all elements
// in range [mid + 1, high] are >= key
// then we search in left side of mid
// so we now search in [low, mid - 1]
high = mid - 1;
}
}
return ans;
}
console.log("Contains");
for (var i = 0; i < 10; i++)
console.log(i, contains(0, n - 1, i));
console.log("First occurrence of key");
for (var i = 0; i < 10; i++)
console.log(i, first(0, n - 1, i));
console.log("Last occurrence of key");
for (var i = 0; i < 10; i++)
console.log(i, last(0, n - 1, i));
console.log("Least integer greater than key");
for (var i = 0; i < 10; i++)
console.log(i, leastgreater(0, n - 1, i));
console.log("Greatest integer lesser than key");
for (var i = 0; i < 10; i++)
console.log(i, greatestlesser(0, n - 1, i));
// This code is contributed by phasing17
Producción:
Contains 0 0 1 0 2 1 3 1 4 0 5 1 6 1 7 0 8 0 9 0 First occurrence of key 0 -1 1 -1 2 0 3 1 4 -1 5 3 6 6 7 -1 8 -1 9 -1 Last occurrence of key 0 -1 1 -1 2 0 3 2 4 -1 5 5 6 7 7 -1 8 -1 9 -1 Least integer greater than key 0 0 1 0 2 1 3 3 4 3 5 6 6 -1 7 -1 8 -1 9 -1 Greatest integer lesser than key 0 -1 1 -1 2 -1 3 0 4 2 5 2 6 5 7 7 8 7 9 7
Aquí está el problema que he mencionado al principio de la publicación: Problema de KCOMPRES en Codechef . Pruébelo y no dude en publicar sus consultas aquí.
Más problemas de práctica de búsqueda binaria
Publicación traducida automáticamente
Artículo escrito por ChandanAkiti y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA