Searching in a Sorted Array using Binary Search
In a sorted array, the search operation can be performed efficiently by using binary search.
Below is the implementation of the above approach:
// C++ program to implement binary search in sorted array
#include <bits/stdc++.h>
using namespace std;
int binarySearch(int arr[], int low, int high, int key)
{
if (high < low)
return -1;
int mid = (low + high) / 2; /*low + (high - low)/2;*/
if (key == arr[mid])
return mid;
if (key > arr[mid])
return binarySearch(arr, (mid + 1), high, key);
return binarySearch(arr, low, (mid - 1), key);
}
/* Driver code */
int main()
{
// Let us search 3 in below array
int arr[] = { 5, 6, 7, 8, 9, 10 };
int n, key;
n = sizeof(arr) / sizeof(arr[0]);
key = 10;
// Function call
cout << "Index: " << binarySearch(arr, 0, n - 1, key)
<< endl;
return 0;
}
// This code is contributed by NamrataSrivastava1
// C program to implement binary search in sorted array
#include <stdio.h>
int binarySearch(int arr[], int low, int high, int key)
{
if (high < low)
return -1;
int mid = (low + high) / 2; /*low + (high - low)/2;*/
if (key == arr[mid])
return mid;
if (key > arr[mid])
return binarySearch(arr, (mid + 1), high, key);
return binarySearch(arr, low, (mid - 1), key);
}
/* Driver Code */
int main()
{
// Let us search 3 in below array
int arr[] = { 5, 6, 7, 8, 9, 10 };
int n, key;
n = sizeof(arr) / sizeof(arr[0]);
key = 10;
// Function call
printf("Index: %d\n", binarySearch(arr, 0, n - 1, key));
return 0;
}
// Java program to implement binary
// search in a sorted array
class Main {
// function to implement
// binary search
static int binarySearch(int arr[], int low, int high,
int key)
{
if (high < low)
return -1;
/*low + (high - low)/2;*/
int mid = (low + high) / 2;
if (key == arr[mid])
return mid;
if (key > arr[mid])
return binarySearch(arr, (mid + 1), high, key);
return binarySearch(arr, low, (mid - 1), key);
}
/* Driver Code*/
public static void main(String[] args)
{
int arr[] = { 5, 6, 7, 8, 9, 10 };
int n, key;
n = arr.length - 1;
key = 10;
// Function call
System.out.println("Index: "
+ binarySearch(arr, 0, n, key));
}
}
# python 3 program to implement
# binary search in sorted array
def binary_search(arr, start, end, key):
# if case is evaluated when element is found else -1 is returned
if (start < end):
mid = (start + end) //2
if (key == arr[mid]):
return mid
if (key < arr[mid]):
return binary_search(arr, start, mid - 1, key)
if (key > arr[mid]):
return binary_search(arr, mid + 1, end, key)
else:
return -1
# Driver code
if __name__ == "__main__":
# Let us take a sorted array to find a key
arr = [11, 20, 39, 44, 57, 63, 72, 88, 94]
key = 72
index = binary_search(arr, 0, len(arr) - 1, key)
if index != -1:
print(f"Element found at index {index}")
else:
print("Element not found")
# This code is contributed by Smitha Dinesh Semwal
# and improved by Rahul Varma
// C# program to implement binary
// search in a sorted array
using System;
public class GFG {
// function to implement
// binary search
public static int binarySearch(int[] arr, int low,
int high, int key)
{
if (high < low) {
return -1;
}
int mid = (low + high) / 2;
if (key == arr[mid]) {
return mid;
}
if (key > arr[mid]) {
return binarySearch(arr, (mid + 1), high, key);
}
return binarySearch(arr, low, (mid - 1), key);
}
/* Driver Code */
public static void Main(string[] args)
{
int[] arr = new int[] { 5, 6, 7, 8, 9, 10 };
int n, key;
n = arr.Length;
key = 10;
// Function call
Console.WriteLine(
"Index: " + binarySearch(arr, 0, n - 1, key));
}
}
// This code is contributed by Shrikant13
// Javascript program to implement
// binary search in sorted array
function binarySearch( arr, low, high, key)
{
if (high < low)
return -1;
/*low + (high - low)/2;*/
let mid = Math.trunc((low + high) / 2);
if (key == arr[mid])
return mid;
if (key > arr[mid])
return binarySearch(arr, (mid + 1), high, key);
return binarySearch(arr, low, (mid - 1), key);
}
// Driver program
// Let us search 3 in below array
let arr = [ 5, 6, 7, 8, 9, 10 ];
let n, key;
n = arr.length;
key = 10;
console.log("Index: " + binarySearch(arr, 0, n - 1, key)
+ "</br>");
<?php
// PHP program to implement
// binary search in sorted array
function binarySearch($arr, $low,
$high, $key)
{
if ($high < $low)
return -1;
$mid = (int)($low + $high) / 2;
if ($key == $arr[(int)$mid])
return $mid;
if ($key > $arr[(int)$mid])
return binarySearch($arr, ($mid + 1),
$high, $key);
return (binarySearch($arr, $low,
($mid -1), $key));
}
// Driver Code
// Let us search 3 in below array
$arr = array(5, 6, 7, 8, 9, 10);
$n = count($arr);
$key = 10;
// Function call
echo "Index: ", (int)binarySearch($arr, 0,
$n-1, $key);
// This code is contributed by
// Srathore
?>
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).
Searching Elements in an Array | Array Operations
In this post, we will look into search operation in an Array, i.e., how to search an element in an Array, such as:
- Searching in an Unsorted Array using Linear Search
- Searching in a Sorted Array using Linear Search
- Searching in a Sorted Array using Binary Search
- Searching in an Sorted Array using Fibonacci Search