Binary Search in Array using Iteration

You are given a sorted array of integers and a target number. Your task is to find the index of the target number using the binary search algorithm, implemented in an iterative way (using loops instead of recursion).

Binary search works only when the array is sorted in ascending order. If the target exists in the array, return its index. Otherwise, return -1.

Step-by-Step Understanding of Binary Search

Before diving into code, let’s first understand what binary search is trying to solve.

Imagine you have a sorted array of numbers, and you're trying to find the index of a particular number (called the target). Instead of checking each number one by one, which can be slow, binary search helps you find the number much faster—by always checking the middle of the current search range and cutting the problem in half at each step.

This method is extremely efficient, with a time complexity of O(log n), making it ideal for searching in large sorted arrays.

Example Problem

Let’s say we are given the sorted array: [2, 4, 6, 8, 10, 12, 14] and we are asked to find the index of the number 10.

Step-by-Step Execution

1. We start with two pointers:
   • low = 0 (start of the array)
   • high = 6 (end of the array)
2. Calculate mid index: mid = Math.floor((0 + 6) / 2) = 3
3. Check the middle element: arr[3] = 8
4. Since 8 < 10, the target must be in the right half, so we set low = mid + 1 = 4
5. Now, low = 4, high = 6. Calculate new mid: mid = Math.floor((4 + 6) / 2) = 5
6. Check arr[5] = 12. Since 12 > 10, we now look in the left half: high = mid - 1 = 4
7. Now, low = 4 and high = 4. So, mid = 4
8. arr[4] = 10 which is the target! Return index 4

How the Algorithm Works

• Keep narrowing the range between low and high
• Each time, compare the middle element to the target
• If it's a match, return the index
• If the target is smaller, search in the left half
• If the target is larger, search in the right half
• Repeat until low exceeds high

Handling Edge Cases

• Target not in the array: Eventually, low > high, and we return -1
• Target smaller than all elements: First mid will already be greater, and we keep moving left until no elements are left
• Target greater than all elements: Mid will always be smaller, we keep moving right until no elements are left
• Empty array: Since low = 0 and high = -1 initially, the loop doesn't run and we return -1
• Single element array:
  • If it matches the target → return index 0
  • If not → return -1

Finally

Binary search is one of the most efficient algorithms for searching in sorted arrays. It’s important to carefully manage the low and high pointers and always check for edge cases like empty arrays or off-bound conditions. Once mastered, binary search becomes a powerful tool in your problem-solving toolkit.

1. Given a sorted array arr and a target value.
2. Initialize two pointers: low = 0 and high = arr.length - 1.
3. Repeat while low ≤ high:
4. → Calculate mid = Math.floor((low + high) / 2).
5. → If arr[mid] == target, return mid (target found).
6. → If arr[mid] < target, set low = mid + 1.
7. → Else, set high = mid - 1.
8. If the loop ends without finding the target, return -1 (not found).

#include <stdio.h>

int binarySearch(int arr[], int size, int target) {
  int low = 0, high = size - 1;
  while (low <= high) {
    int mid = low + (high - low) / 2;
    if (arr[mid] == target) return mid;
    else if (arr[mid] < target) low = mid + 1;
    else high = mid - 1;
  }
  return -1;
}

int main() {
  int arr[] = {1, 3, 5, 7, 9, 11};
  int size = sizeof(arr) / sizeof(arr[0]);
  int target = 7;
  printf("Index: %d\n", binarySearch(arr, size, target));
  return 0;
}

#include <iostream>
#include <vector>
using namespace std;

int binarySearch(vector<int>& arr, int target) {
  int low = 0, high = arr.size() - 1;
  while (low <= high) {
    int mid = low + (high - low) / 2;
    if (arr[mid] == target) return mid;
    else if (arr[mid] < target) low = mid + 1;
    else high = mid - 1;
  }
  return -1;
}

int main() {
  vector<int> arr = {1, 3, 5, 7, 9, 11};
  int target = 7;
  cout << "Index: " << binarySearch(arr, target) << endl;
  return 0;
}

def binary_search(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

# Sample Input
arr = [1, 3, 5, 7, 9, 11]
target = 7
print("Index:", binary_search(arr, target))

public class BinarySearch {
  public static int binarySearch(int[] arr, int target) {
    int low = 0, high = arr.length - 1;
    while (low <= high) {
      int mid = (low + high) / 2;
      if (arr[mid] == target) return mid;
      else if (arr[mid] < target) low = mid + 1;
      else high = mid - 1;
    }
    return -1;
  }

  public static void main(String[] args) {
    int[] arr = {1, 3, 5, 7, 9, 11};
    int target = 7;
    System.out.println("Index: " + binarySearch(arr, target));
  }
}

function binarySearch(arr, target) {
  let low = 0, high = arr.length - 1;
  while (low <= high) {
    let mid = Math.floor((low + high) / 2);
    if (arr[mid] === target) return mid;
    else if (arr[mid] < target) low = mid + 1;
    else high = mid - 1;
  }
  return -1;
}

// Sample Input
const arr = [1, 3, 5, 7, 9, 11];
const target = 7;
console.log("Index:", binarySearch(arr, target));

package main

import (
  "fmt"
)

func binarySearch(arr []int, target int) int {
  low, high := 0, len(arr)-1
  for low <= high {
    mid := (low + high) / 2
    if arr[mid] == target {
      return mid
    } else if arr[mid] < target {
      low = mid + 1
    } else {
      high = mid - 1
    }
  }
  return -1
}

func main() {
  arr := []int{1, 3, 5, 7, 9, 11}
  target := 7
  fmt.Println("Index:", binarySearch(arr, target))
}

fn binary_search(arr: &[i32], target: i32) -> i32 {
    let mut low = 0;
    let mut high = arr.len() as i32 - 1;
    while low <= high {
        let mid = (low + high) / 2;
        if arr[mid as usize] == target {
            return mid;
        } else if arr[mid as usize] < target {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    -1
}

fn main() {
    let arr = [1, 3, 5, 7, 9, 11];
    let target = 7;
    println!("Index: {}", binary_search(&arr, target));
}

fun binarySearch(arr: IntArray, target: Int): Int {
    var low = 0
    var high = arr.size - 1
    while (low <= high) {
        val mid = (low + high) / 2
        when {
            arr[mid] == target -> return mid
            arr[mid] < target -> low = mid + 1
            else -> high = mid - 1
        }
    }
    return -1
}

fun main() {
    val arr = intArrayOf(1, 3, 5, 7, 9, 11)
    val target = 7
    println("Index: ${binarySearch(arr, target)}")
}

func binarySearch(_ arr: [Int], _ target: Int) -> Int {
    var low = 0, high = arr.count - 1
    while low <= high {
        let mid = (low + high) / 2
        if arr[mid] == target {
            return mid
        } else if arr[mid] < target {
            low = mid + 1
        } else {
            high = mid - 1
        }
    }
    return -1
}

let arr = [1, 3, 5, 7, 9, 11]
let target = 7
print("Index: \(binarySearch(arr, target))")

function binarySearch(arr: number[], target: number): number {
  let low = 0, high = arr.length - 1;
  while (low <= high) {
    const mid = Math.floor((low + high) / 2);
    if (arr[mid] === target) return mid;
    else if (arr[mid] < target) low = mid + 1;
    else high = mid - 1;
  }
  return -1;
}

// Sample Input
const arr: number[] = [1, 3, 5, 7, 9, 11];
const target: number = 7;
console.log("Index:", binarySearch(arr, target));

Time complexity

Space complexity

O(1)

The algorithm uses constant space. It only maintains a few variables (like low, high, and mid) and does not allocate extra space based on input size.