document.write( "Index: "+ binarySearch(arr, 0, n - 1, key)
+ "</br>");
</script>
Output
Index: 5
Time Complexity: O(log(n)) Using Binary Search Auxiliary Space: O(log(n)) due to recursive calls, otherwise iterative version uses Auxiliary Space of O(1).
How to Insert in a Sorted Array?
In a sorted array, a search operation is performed for the possible position of the given element by using Binary search, and then an insert operation is performed followed by shifting the elements. And in an unsorted array, the insert operation is faster as compared to the sorted array because we don’t have to care about the position at which the element is placed.
Below is the implementation of the above approach:
C++
// C++ program to implement insert operation in
// an sorted array.
#include <bits/stdc++.h>
usingnamespacestd;
// Inserts a key in arr[] of given capacity. n is current
// size of arr[]. This function returns n+1 if insertion
Before Insertion: 12 16 20 40 50 70
After Insertion: 12 16 20 26 40 50 70
Time Complexity: O(N) [In the worst case all elements may have to be moved] Auxiliary Space: O(1)
How to Delete in a Sorted Array?
In the delete operation, the element to be deleted is searched using binary search, and then the delete operation is performed followed by shifting the elements.
Performing delete operation
Below is the implementation of the above approach:
# Python program to implement delete operation in a
# sorted array
# /* Function to delete an element */
defdeleteElement(arr, n, key):
# Find position of element to be deleted
pos =binarySearch(arr, 0, n -1, key)
if(pos ==-1):
print("Element not found")
returnn
# Deleting element
fori inrange(pos, n -1):
arr[i] =arr[i +1]
returnn -1
# To search a key to be deleted
defbinarySearch(arr, low, high, key):
if(high < low):
return-1
mid =(low +high) //2
if(key ==arr[mid]):
returnmid
if(key > arr[mid]):
returnbinarySearch(arr, (mid +1), high, key)
returnbinarySearch(arr, low, (mid -1), key)
# Driver code
if__name__ =="__main__":
arr =[10, 20, 30, 40, 50]
n =len(arr)
key =30
print("Array before deletion")
fori inrange(n):
print(arr[i], end=" ")
# Function call
n =deleteElement(arr, n, key)
print("\n\nArray after deletion")
fori inrange(n):
print(arr[i], end=" ")
# This code is contributed by shubhamsingh10
C#
// C# program to delete an
// element from a sorted array
usingSystem;
publicclassGFG {
// Binary search
staticintbinarySearch(int[] arr, intlow, inthigh,
intkey)
{
if(high < low)
return-1;
intmid = (low + high) / 2;
if(key == arr[mid])
returnmid;
if(key > arr[mid])
returnbinarySearch(arr, (mid + 1), high, key);
returnbinarySearch(arr, low, (mid - 1), key);
}
/* Function to delete an element */
staticintdeleteElement(int[] arr, intn, intkey)
{
// Find position of element to be deleted
intpos = binarySearch(arr, 0, n - 1, key);
if(pos == -1) {
Console.WriteLine("Element not found");
returnn;
}
// Deleting element
inti;
for(i = pos; i < n - 1; i++)
arr[i] = arr[i + 1];
returnn - 1;
}
/* Driver Code */
publicstaticvoidMain()
{
inti;
int[] arr = { 10, 20, 30, 40, 50 };
intn = arr.Length;
intkey = 30;
Console.Write("Array before deletion:\n");
for(i = 0; i < n; i++)
Console.Write(arr[i] + " ");
// Function call
n = deleteElement(arr, n, key);
Console.Write("\n\nArray after deletion:\n");
for(i = 0; i < n; i++)
Console.Write(arr[i] + " ");
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript program to delete an
// element from a sorted array
// binary search
functionbinarySearch(arr, low, high, key)
{
if(high < low)
return-1;
let mid = (low + high) / 2;
if(key == arr[mid])
returnmid;
if(key > arr[mid])
returnbinarySearch(arr, (mid + 1), high, key);
returnbinarySearch(arr, low, (mid - 1), key);
}
/* Function to delete an element */
functiondeleteElement( arr, n, key)
{
// Find position of element to be deleted
let pos = binarySearch(arr, 0, n - 1, key);
if(pos == -1) {
document.write("Element not found");
returnn;
}
// Deleting element
let i;
for(i = pos; i < n - 1; i++)
arr[i] = arr[i + 1];
returnn - 1;
}
/* Driver Code */
let i;
let arr = [ 10, 20, 30, 40, 50 ];
let n = arr.length;
let key = 30;
document.write("Array before deletion:\n");
for(i = 0; i < n; i++)
document.write(arr[i] + " ");
n = deleteElement(arr, n, key);
document.write("<br>"+"Array after deletion:\n");
for(i = 0; i < n; i++)
document.write(arr[i] + " ");
// this code is contributed by shivanisinghss2110
</script>
Output
Array before deletion
10 20 30 40 50
Array after deletion
10 20 40 50
Time Complexity: O(N). In the worst case all elements may have to be moved Auxiliary Space: O(log N). An implicit stack will be used
If you like neveropen and would like to contribute, you can also write an article and mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks. Please write comments if you find anything incorrect, or if you want to share more information about the topic discussed above
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!