# How to implement binary search using iterative method

One of the most fundamental algorithms in computer science is the binary search algorithm. You can implement binary search using two methods: the iterative method and the recursive method. While both methods have the same time complexity, the iterative method is much more efficient in terms of spatial complexity.

The iterative method has a spatial complexity of **O(1)** compared to **O(connection)** produced by the recursive method. So how can you implement the binary search algorithm using the iterative method in C, C++ and Python?

## What is Binary Search?

Binary search, also known as half-range search, logarithmic search, or binary hash, is an algorithm that finds and returns the position of an element in a sorted array. The search item is compared to the middle item. By taking the average of the lower and upper bounds, you can find the intermediate elements.

If the search item is larger than the middle item, that means all the items on the left side are smaller than the search item. So the control moves to the right side of the array (if the array is in ascending order) increasing the lower bound to the next position of the middle element.

Similarly, if the search item is smaller than the middle item, it means that all the items on the right side are larger than the search item. Thus, the control moves to the left part of the array, changing the upper bound to the previous position of the middle element.

This greatly reduces the number of comparisons compared to the implementation of linear search where the number of comparisons equals the number of elements in the worst case. This method is very useful for finding numbers in a phone book or words in a dictionary.

Here is a schematic representation of the binary search algorithm:

## Binary search using C

Follow these steps to implement binary search using C:

The entire source code of the binary search program using C, C++, Java and Python is present in this GitHub repository.

The program defines a function, **binary search()**which returns either the index of the found value or **-1** if not present:

`#include <stdio.h>`int binarySearch(int arr[], int arr_size, int search_number) {

}

The function works by iteratively reducing the search space. Since binary search works on sorted arrays, you can calculate the midpoint, which wouldn’t make sense otherwise. You can either ask the user for a sorted array or use sorting algorithms such as bubble or selection sort.

The **down** and **high** variables store indexes that represent the boundaries of the current search space. **environment** store the index in the middle:

` int low = 0, high = arr_size - 1, mid;`

The main **while()** loop will reduce the search space. If the value of the low index becomes greater than the high index, then the search space has been exhausted, so the value cannot be present.

` while (low <= high) {`

}return -1;

After updating the midpoint at the start of the loop, there are three possible outcomes:

- If the value in the middle is what we’re looking for, return that index.
- If the middle value is higher than what we are looking for, reduce the high.
- If the median value is lower, increase the low.

` `

mid = (low + (high - low)) / 2;if (arr[mid] == search_number)

return mid;

else if (arr[mid] > search_number)

high = mid - 1;

else

low = mid + 1;

Test the function with user input. Use** scanf()** to get input from the command line, including the size of the array, its contents, and a number to search for:

`int main() {`

int arr[100], i, arr_size, search_number;

printf("Enter number of elements: ");

scanf("%d", &arr_size);

printf("Please enter numbers: ");for (i = 0; i < arr_size; i++) {

scanf("%d", &arr[i]);

}

printf("Enter number to be searched: ");

scanf("%d", &search_number);

i = binarySearch(arr, arr_size, search_number);

if (i==-1)

printf("Number not present");

else

printf("Number is present at position %d", i + 1);

return 0;

}

If you find the number, display its position or index, otherwise a message indicating that the number is not present.

## Binary search in C++

You can convert the C program to C++ program by importing the **Input output stream** and **use std namespace** to avoid repeating it several times throughout the program.

`#include <iostream>`

using namespace std;

Use **listen **with extraction operator ** instead of printf() and five with insertion operator >> instead of scanf() and your C++ program is ready.**

`printf("Enter number of elements: ");`

cout << "Enter number of elements: ";

scanf("%d", &arr_size);

cin >> arr_size;

## Binary search using Python

Since Python doesn’t have built-in support for arrays, use lists. Define a function, **binary search()**which accepts three parameters, the list, its size and a number to search for:

`def binarySearch(arr, arr_size, search_number):`

low = 0

high = arr_size - 1

while low <= high:

mid = low + (high-low)

if arr[mid] == search_number:

return mid

elif arr[mid] > search_number:

high = mid - 1

else:

low = mid + 1

return -1

Initialize two variables,** down** and **high**, to serve as the lower and upper bound of the list. Similar to the C implementation, use a **while **loop that reduces the search space. Initialize **environment** to store the median value of the list. Python provides the floor division operator (//) which provides the largest integer possible.

Perform the comparisons and reduce the search space until the median value equals the search number. If the search number is not present, the command will return **-1**.

`arr_size = int(input("Enter number of elements: "))`

arr=[]

print("Please enter numbers: ", end=" ")

for i in range(0,arr_size):

arr.append(int(input()))

search_number = int(input("Enter number to be searched: "))

result = binarySearch(arr, arr_size, search_number)

if result == -1:

print("Number not present")

else:

print("Number is present at position ", (result + 1))

Test the function with user input. Use **to input() **to get the size of the list, its contents, and a number to search for. Use **entire()** to cast Python’s default accepted string input to an integer. To add numbers to the list, use the **to add()** function.

Call **binary search() **and pass the arguments. If you find the number, display its position or index, otherwise a message indicating that the number is not present.

## Binary Search Algorithm Output

Here is the output of the binary search algorithm when the element is present in the array:

Here is the output of the binary search algorithm when the element is not present in the array:

## Learn fundamental data structures and algorithms

Research is one of the first algorithms you learn and is often requested in coding contests, internships, and interviews. Some other algorithms you should learn are sorting, hashing, dynamic programming, string matching, and primality testing algorithms.

Moreover, it is essential to understand the temporal and spatial complexity of the algorithms. They are one of the most crucial concepts in computer science for determining the efficiency of any algorithm. With knowledge of data structures and algorithms, you are bound to build the best programs.