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).

O(1)

Explanation: 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.