Understanding Binary Search

Binary search is a fundamental searching algorithm that efficiently finds the position of a target value in a sorted array. Unlike linear search that scans the elements one by one, binary search reduces the search space by half at each step.

Imagine you are searching for a specific word in a dictionary. Instead of starting from the first page and flipping through each page, you can divide the dictionary in half and quickly determine which half contains the word. Repeat the process with the selected half until you narrow down to the exact location of the word. Binary search follows a similar approach but with numbers.

Let's take a look at an example to understand how binary search works:

1int[] sortedArray = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
2int target = 23;
3int index = binarySearch(sortedArray, target);
4if (index != -1) {
5  System.out.println("Element found at index: " + index);
6} else {
7  System.out.println("Element not found");
8}
9
10public static int binarySearch(int[] arr, int target) {
11  int left = 0;
12  int right = arr.length - 1;
13
14  while (left <= right) {
15    int mid = left + (right - left) / 2;
16
17    if (arr[mid] == target) {
18      return mid;
19    }
20
21    if (arr[mid] < target) {
22      left = mid + 1;
23    } else {
24      right = mid - 1;
25    }
26  }
27
28  return -1;
29}

In this example, we have a sorted array sortedArray containing elements [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]. We want to find the index of the target element which is 23. The binarySearch method takes the sorted array and the target value as parameters and performs the binary search algorithm to find the target value. If the target value is found, the method returns the index of the element; otherwise, it returns -1.

The binary search algorithm first initializes two pointers, left and right, representing the range of indices to search within. In each iteration, the algorithm calculates the middle index using the formula mid = left + (right - left) / 2 and compares the value at the middle index with the target value.

• If the value at the middle index is equal to the target value, the algorithm returns the middle index as the position of the target value.
• If the value at the middle index is less than the target value, the algorithm updates the left pointer to mid + 1 and continues searching in the right half of the array.
• If the value at the middle index is greater than the target value, the algorithm updates the right pointer to mid - 1 and continues searching in the left half of the array.

The binary search algorithm repeats this process until it either finds the target value or concludes that the target value does not exist in the array.

Binary search has a time complexity of O(log(n)), where n represents the number of elements in the array. This logarithmic complexity allows binary search to quickly find the target value even in large sorted arrays. Compared to linear search, which has a time complexity of O(n), binary search offers significant performance improvements when searching in sorted arrays.

Now that you understand the binary search algorithm, take some time to experiment with different sorted arrays and target values. See how the algorithm performs and compare its efficiency with linear search.

xxxxxxxxxx

}

class Main {

  public static void main(String[] args) {

    // replace with your Java logic here

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

    int target = 23;

    int index = binarySearch(sortedArray, target);

    if (index != -1) {

      System.out.println("Element found at index: " + index);

    } else {

      System.out.println("Element not found");

    }

  }

​

  public static int binarySearch(int[] arr, int target) {

    int left = 0;

    int right = arr.length - 1;

​

    while (left <= right) {

      int mid = left + (right - left) / 2;

​

      if (arr[mid] == target) {

        return mid;

      }

​

      if (arr[mid] < target) {

        left = mid + 1;

      } else {

        right = mid - 1;

      }