Iterative Binary Search Algorithm
Here we use a while loop to continue the process of comparing the key and splitting the search space in two halves.
Implementation of Iterative Binary Search Algorithm:
// C++ program to implement iterative Binary Search
#include <bits/stdc++.h>
using namespace std;
// An iterative binary search function.
int binarySearch(int arr[], int low, int high, int x)
{
while (low <= high) {
int mid = low + (high - low) / 2;
// Check if x is present at mid
if (arr[mid] == x)
return mid;
// If x greater, ignore left half
if (arr[mid] < x)
low = mid + 1;
// If x is smaller, ignore right half
else
high = mid - 1;
}
// If we reach here, then element was not present
return -1;
}
// Driver code
int main(void)
{
int arr[] = { 2, 3, 4, 10, 40 };
int x = 10;
int n = sizeof(arr) / sizeof(arr[0]);
int result = binarySearch(arr, 0, n - 1, x);
(result == -1)
? cout << "Element is not present in array"
: cout << "Element is present at index " << result;
return 0;
}
// C program to implement iterative Binary Search
#include <stdio.h>
// An iterative binary search function.
int binarySearch(int arr[], int low, int high, int x)
{
while (low <= high) {
int mid = low + (high - low) / 2;
// Check if x is present at mid
if (arr[mid] == x)
return mid;
// If x greater, ignore left half
if (arr[mid] < x)
low = mid + 1;
// If x is smaller, ignore right half
else
high = mid - 1;
}
// If we reach here, then element was not present
return -1;
}
// Driver code
int main(void)
{
int arr[] = { 2, 3, 4, 10, 40 };
int n = sizeof(arr) / sizeof(arr[0]);
int x = 10;
int result = binarySearch(arr, 0, n - 1, x);
(result == -1) ? printf("Element is not present"
" in array")
: printf("Element is present at "
"index %d",
result);
return 0;
}
// Java implementation of iterative Binary Search
import java.io.*;
class BinarySearch {
// Returns index of x if it is present in arr[].
int binarySearch(int arr[], int x)
{
int low = 0, high = arr.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
// Check if x is present at mid
if (arr[mid] == x)
return mid;
// If x greater, ignore left half
if (arr[mid] < x)
low = mid + 1;
// If x is smaller, ignore right half
else
high = mid - 1;
}
// If we reach here, then element was
// not present
return -1;
}
// Driver code
public static void main(String args[])
{
BinarySearch ob = new BinarySearch();
int arr[] = { 2, 3, 4, 10, 40 };
int n = arr.length;
int x = 10;
int result = ob.binarySearch(arr, x);
if (result == -1)
System.out.println(
"Element is not present in array");
else
System.out.println("Element is present at "
+ "index " + result);
}
}
# Python3 code to implement iterative Binary
# Search.
# It returns location of x in given array arr
def binarySearch(arr, low, high, x):
while low <= high:
mid = low + (high - low) // 2
# Check if x is present at mid
if arr[mid] == x:
return mid
# If x is greater, ignore left half
elif arr[mid] < x:
low = mid + 1
# If x is smaller, ignore right half
else:
high = mid - 1
# If we reach here, then the element
# was not present
return -1
# Driver Code
if __name__ == '__main__':
arr = [2, 3, 4, 10, 40]
x = 10
# Function call
result = binarySearch(arr, 0, len(arr)-1, x)
if result != -1:
print("Element is present at index", result)
else:
print("Element is not present in array")
// C# implementation of iterative Binary Search
using System;
class GFG {
// Returns index of x if it is present in arr[]
static int binarySearch(int[] arr, int x)
{
int low = 0, high = arr.Length - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
// Check if x is present at mid
if (arr[mid] == x)
return mid;
// If x greater, ignore left half
if (arr[mid] < x)
low = mid + 1;
// If x is smaller, ignore right half
else
high = mid - 1;
}
// If we reach here, then element was
// not present
return -1;
}
// Driver code
public static void Main()
{
int[] arr = { 2, 3, 4, 10, 40 };
int n = arr.Length;
int x = 10;
int result = binarySearch(arr, x);
if (result == -1)
Console.WriteLine(
"Element is not present in array");
else
Console.WriteLine("Element is present at "
+ "index " + result);
}
}
// Program to implement iterative Binary Search
// A iterative binary search function. It returns
// location of x in given array arr[l..r] is present,
// otherwise -1
function binarySearch(arr, x)
{
let low = 0;
let high = arr.length - 1;
let mid;
while (high >= low) {
mid = low + Math.floor((high - low) / 2);
// If the element is present at the middle
// itself
if (arr[mid] == x)
return mid;
// If element is smaller than mid, then
// it can only be present in left subarray
if (arr[mid] > x)
high = mid - 1;
// Else the element can only be present
// in right subarray
else
low = mid + 1;
}
// We reach here when element is not
// present in array
return -1;
}
arr =new Array(2, 3, 4, 10, 40);
x = 10;
n = arr.length;
result = binarySearch(arr, x);
(result == -1) ? console.log("Element is not present in array")
: console.log ("Element is present at index " + result);
// This code is contributed by simranarora5sos and rshuklabbb
<?php
// PHP program to implement
// iterative Binary Search
// An iterative binary search
// function
function binarySearch($arr, $low,
$high, $x)
{
while ($low <= $high)
{
$mid = $low + ($high - $low) / 2;
// Check if x is present at mid
if ($arr[$mid] == $x)
return floor($mid);
// If x greater, ignore
// left half
if ($arr[$mid] < $x)
$low = $mid + 1;
// If x is smaller,
// ignore right half
else
$high = $mid - 1;
}
// If we reach here, then
// element was not present
return -1;
}
// Driver Code
$arr = array(2, 3, 4, 10, 40);
$n = count($arr);
$x = 10;
$result = binarySearch($arr, 0,
$n - 1, $x);
if(($result == -1))
echo "Element is not present in array";
else
echo "Element is present at index ",
$result;
// This code is contributed by anuj_67.
?>
Output
Element is present at index 3
Time Complexity: O(log N)
Auxiliary Space: O(1)
Binary Search Algorithm – Iterative and Recursive Implementation
Binary Search Algorithm is a searching algorithm used in a sorted array by repeatedly dividing the search interval in half. The idea of binary search is to use the information that the array is sorted and reduce the time complexity to O(log N).