Dada una array, la tarea es crear una nueva array ordenada en orden ascendente a partir de los elementos de la array dada.
Ejemplos:
Input : arr[] = {2, 5, 4, 9, 8}
Output : 2 4 5 8 9
Input : arr[] = {10, 45, 98, 35, 45}
Output : 10 35 45 45 98
El problema anterior se puede resolver de manera eficiente utilizando la búsqueda binaria. Creamos una nueva array e insertamos el primer elemento si está vacío. Ahora, para cada elemento nuevo, encontramos la posición correcta para el elemento en la nueva array mediante la búsqueda binaria y luego insertamos ese elemento en el índice correspondiente en la nueva array.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to create a sorted array
// using Binary Search
#include <bits/stdc++.h>
using namespace std;
// Function to create a new sorted array
// using Binary Search
void createSorted(int a[], int n)
{
// Auxiliary Array
vector<int> b;
for (int j = 0; j < n; j++) {
// if b is empty any element can be at
// first place
if (b.empty())
b.push_back(a[j]);
else {
// Perform Binary Search to find the correct
// position of current element in the
// new array
int start = 0, end = b.size() - 1;
// let the element should be at first index
int pos = 0;
while (start <= end) {
int mid = start + (end - start) / 2;
// if a[j] is already present in the new array
if (b[mid] == a[j]) {
// add a[j] at mid+1. you can add it at mid
b.emplace(b.begin() + max(0, mid + 1), a[j]);
break;
}
// if a[j] is lesser than b[mid] go right side
else if (b[mid] > a[j])
// means pos should be between start and mid-1
pos = end = mid - 1;
else
// else pos should be between mid+1 and end
pos = start = mid + 1;
// if a[j] is the largest push it at last
if (start > end) {
pos = start;
b.emplace(b.begin() + max(0, pos), a[j]);
// here max(0, pos) is used because sometimes
// pos can be negative as smallest duplicates
// can be present in the array
break;
}
}
}
}
// Print the new generated sorted array
for (int i = 0; i < n; i++)
cout << b[i] << " ";
}
// Driver Code
int main()
{
int a[] = { 2, 5, 4, 9, 8 };
int n = sizeof(a) / sizeof(a[0]);
createSorted(a, n);
return 0;
}
Java
// Java program to create a sorted array
// using Binary Search
import java.util.*;
class GFG
{
// Function to create a new sorted array
// using Binary Search
static void createSorted(int a[], int n)
{
// Auxiliary Array
Vector<Integer> b = new Vector<>();
for (int j = 0; j < n; j++)
{
// if b is empty any element can be at
// first place
if (b.isEmpty())
b.add(a[j]);
else
{
// Perform Binary Search to find the correct
// position of current element in the
// new array
int start = 0, end = b.size() - 1;
// let the element should be at first index
int pos = 0;
while (start <= end)
{
int mid = start + (end - start) / 2;
// if a[j] is already present in the new array
if (b.get(mid) == a[j])
{
// add a[j] at mid+1. you can add it at mid
b.add((Math.max(0, mid + 1)), a[j]);
break;
}
// if a[j] is lesser than b[mid] go right side
else if (b.get(mid) > a[j])
// means pos should be between start and mid-1
pos = end = mid - 1;
else
// else pos should be between mid+1 and end
pos = start = mid + 1;
// if a[j] is the largest push it at last
if (start > end)
{
pos = start;
b.add(Math.max(0, pos), a[j]);
// here max(0, pos) is used because sometimes
// pos can be negative as smallest duplicates
// can be present in the array
break;
}
}
}
}
// Print the new generated sorted array
for (int i = 0; i < n; i++)
System.out.print(b.get(i) + " ");
}
// Driver Code
public static void main(String args[])
{
int a[] = { 2, 5, 4, 9, 8 };
int n = a.length;
createSorted(a, n);
}
}
/* This code is contributed by PrinciRaj1992 */
Python3
# Python program to create a sorted array # using Binary Search # Function to create a new sorted array # using Binary Search def createSorted(a: list, n: int): # Auxiliary Array b = [] for j in range(n): # if b is empty any element can be at # first place if len(b) == 0: b.append(a[j]) else: # Perform Binary Search to find the correct # position of current element in the # new array start = 0 end = len(b) - 1 # let the element should be at first index pos = 0 while start <= end: mid = start + (end - start) // 2 # if a[j] is already present in the new array if b[mid] == a[j]: # add a[j] at mid+1. you can add it at mid b.insert(max(0, mid + 1), a[j]) break # if a[j] is lesser than b[mid] go right side elif b[mid] > a[j]: # means pos should be between start and mid-1 pos = end = mid - 1 else: # else pos should be between mid+1 and end pos = start = mid + 1 # if a[j] is the largest push it at last if start > end: pos = start b.insert(max(0, pos), a[j]) # here max(0, pos) is used because sometimes # pos can be negative as smallest duplicates # can be present in the array break # Print the new generated sorted array for i in range(n): print(b[i], end=" ") # Driver Code if __name__ == "__main__": a = [2, 5, 4, 9, 8] n = len(a) createSorted(a, n) # This code is contributed by # sanjeev2552
C#
// C# program to create a sorted array
// using Binary Search
using System;
using System.Collections.Generic;
class GFG
{
// Function to create a new sorted array
// using Binary Search
static void createSorted(int []a, int n)
{
// Auxiliary Array
List<int> b = new List<int>();
for (int j = 0; j < n; j++)
{
// if b is empty any element can be at
// first place
if (b.Count == 0)
b.Add(a[j]);
else
{
// Perform Binary Search to find the correct
// position of current element in the
// new array
int start = 0, end = b.Count - 1;
// let the element should be at first index
int pos = 0;
while (start <= end)
{
int mid = start + (end - start) / 2;
// if a[j] is already present in the new array
if (b[mid] == a[j])
{
// add a[j] at mid+1. you can add it at mid
b.Insert((Math.Max(0, mid + 1)), a[j]);
break;
}
// if a[j] is lesser than b[mid] go right side
else if (b[mid] > a[j])
// means pos should be between start and mid-1
pos = end = mid - 1;
else
// else pos should be between mid+1 and end
pos = start = mid + 1;
// if a[j] is the largest push it at last
if (start > end)
{
pos = start;
b.Insert(Math.Max(0, pos), a[j]);
// here Max(0, pos) is used because sometimes
// pos can be negative as smallest duplicates
// can be present in the array
break;
}
}
}
}
// Print the new generated sorted array
for (int i = 0; i < n; i++)
Console.Write(b[i] + " ");
}
// Driver Code
public static void Main(String []args)
{
int []a = { 2, 5, 4, 9, 8 };
int n = a.Length;
createSorted(a, n);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript program to create a sorted array
// using Binary Search
// Function to create a new sorted array
// using Binary Search
function createSorted(a, n) {
// Auxiliary Array
var b = [];
for (var j = 0; j < n; j++) {
// if b is empty any element can be at
// first place
if (b.length == 0) b.push(a[j]);
else {
// Perform Binary Search to find the correct
// position of current element in the
// new array
var start = 0,
end = b.length - 1;
// let the element should be at first index
var pos = 0;
while (start <= end) {
var mid = start + parseInt((end - start) / 2);
// if a[j] is already present in the new array
if (b[mid] === a[j]) {
// add a[j] at mid+1. you can add it at mid
b.insert(Math.max(0, mid + 1), a[j]);
break;
}
// if a[j] is lesser than b[mid] go right side
else if (b[mid] > a[j])
// means pos should be between start and mid-1
pos = end = mid - 1;
// else pos should be between mid+1 and end
else pos = start = mid + 1;
// if a[j] is the largest push it at last
if (start > end) {
pos = start;
b.insert(Math.max(0, pos), a[j]);
// here Max(0, pos) is used because sometimes
// pos can be negative as smallest duplicates
// can be present in the array
break;
}
}
}
}
// Print the new generated sorted array
for (var i = 0; i < n; i++) document.write(b[i] + " ");
}
Array.prototype.insert = function (index, item) {
this.splice(index, 0, item);
};
// Driver Code
var a = [2, 5, 4, 9, 8];
var n = a.length;
createSorted(a, n);
</script>
Producción:
2 4 5 8 9
Complejidad temporal : O(N*N). Aunque se utiliza la búsqueda binaria, las llamadas de inserción de lista se ejecutan en tiempo O(N) en promedio
Espacio auxiliar : O(N)
Publicación traducida automáticamente
Artículo escrito por Bhashkar_P y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA