Binary Search Java

Binary search is a fundamental algorithm that is used to efficiently locate a specific element within a sorted array. It has a time complexity of O(log n), making it significantly faster than linear search, which has a time complexity of O(n).

In order to implement binary search in Java, it is important to first ensure that the array being searched is sorted. This can be done using a sorting algorithm such as quicksort or mergesort.

There are two common approaches to implementing binary search: iterative and recursive. The iterative approach involves using a loop to repeatedly divide the search interval in half until the element is found, while the recursive approach involves using a recursive function to continually divide the search interval in half until the element is found.

Here is an example of binary search implemented using an iterative approach:

public class BinarySearch {
  public static int binarySearch(int[] arr, int x) {
    int low = 0;
    int high = arr.length - 1;
    int mid;

    while (low <= high) {
      mid = low + (high - low) / 2;

      if (arr[mid] < x) {
        low = mid + 1;
      } else if (arr[mid] > x) {
        high = mid - 1;
      } else {
        return mid;
      }
    }

    return -1;
  }
}

And here is an example of binary search implemented using a recursive approach:

public class BinarySearch {
  public static int binarySearch(int[] arr, int x, int low, int high) {
    if (low > high) {
      return -1;
    }

    int mid = low + (high - low) / 2;

    if (arr[mid] < x) {
      return binarySearch(arr, x, mid + 1, high);
    } else if (arr[mid] > x) {
      return binarySearch(arr, x, low, mid - 1);
    } else {
      return mid;
    }
  }
}

It is important to thoroughly test your implementation of binary search to ensure that it is working correctly and efficiently. This can be done by testing with various sizes and types of input data, as well as edge cases such as the element not being present in the array.

By using binary search, you can improve the performance of your code and effectively locate specific elements within a sorted array.