Binary Search on a Single-Dimensional Array

Binary search is a widely used searching algorithm that is efficient for sorted arrays. It works by repeatedly dividing the search space in half, comparing the target value with the middle element, and narrowing down the search range until the target value is found or determined to be absent.

How Binary Search Works

  1. Start by examining the middle element of the array.
  2. If the middle element matches the target value, the search is complete.
  3. If the target value is less than the middle element, narrow down the search to the left half of the array.
  4. If the target value is greater than the middle element, focus the search on the right half of the array.
  5. Repeat steps 2-4 until the target value is found or the search range is empty.
↑

Let’s consider an example to illustrate the binary search algorithm. Suppose we have the following sorted array:

int[] array = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};

We want to find the index of the target value 23 using binary search.

  1. Initially, the search range is the entire array. The lower bound is 0, and the upper bound is 9 (array.length – 1).
  2. Calculate the middle index as the average of the lower and upper bounds: int mid = (0 + 9) / 2 = 4.
  3. Compare the middle element array[mid] with the target value to determine a match with the value 23.
  4. Since array[mid] (16) is less than the target value, we update the lower bound to mid + 1 = 5 and repeat the process.
  5. Calculate the new middle index: mid = (5 + 9) / 2 = 7.
  6. Compare array[mid] (56) with the target value.
  7. Since array[mid] is greater than the target value, we update the upper bound to mid - 1 = 6 and repeat the process.
  8. Calculate the new middle index: mid = (5 + 6) / 2 = 5.
  9. Compare array[mid] (23) with the target value.
  10. The target value matches the middle element, so the search is complete. The index of 23 in the array is 5.
↑

Implementation of Binary Search in Java

public class BinarySearch {
public static void main(String[] args) {
int[] array = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
int target = 23;
    int left = 0;
    int right = array.length - 1;
    int result = -1; // Variable to store the index of the target value

    while (left <= right) {
        int mid = left + right  / 2;

        if (array[mid] == target) {
            result = mid;
            break;
        }

        if (array[mid] < target)
            left = mid + 1;
        else
            right = mid - 1;
    }

    if (result == -1)
        System.out.println("Target value not found");
    else
        System.out.println("Target value found at index " + result);
}
}
↑
  1. Input: We start with a sorted one-dimensional array and a target value that we want to search for.
  2. Initialization: We initialize two variables, left and right, to represent the bounds of the search space. Initially, left is set to the index of the first element in the array (0), and right is set to the index of the last element (array.length – 1).
  3. Search Iteration: We enter a loop that continues until the left index is less than or equal to the right index. This condition ensures that the search space is not empty.
  4. Calculate the Middle Index: Inside the loop, we calculate the middle index of the current search space using the formula: mid = left + right / 2.
  5. Compare with the Middle Element: We compare the target value with the element at the middle index, array[mid].
    • If array[mid] is equal to the target value, we have found a match, and we can return the index mid.
    • If array[mid] is less than the target value, we update the left index to mid + 1 and repeat the search in the right half of the array.
    • If array[mid] is greater than the target value, we update the right index to mid - 1 and repeat the search in the left half of the array.
  6. Target Not Found: If the loop terminates without finding a match, the target value is not present in the array. In this case, we use a sentinel value, such as -1, to indicate that the target value was not found.
↑

Conclusion

Binary search is a powerful algorithm for searching sorted arrays. Its efficiency stems from dividing the search space in half at each step, resulting in a time complexity of O(log n). By understanding and implementing binary search, you can significantly improve the performance of your search operations on sorted arrays.

I hope this tutorial post helps you understand binary search on a single-dimensional array using Java and BlueJ. Feel free to reach out if you have any further questions!

↑