BinarySearch.md

Binary Search

(Algorithm)

• Binary search is one of the searching techniques applied when the input is sorted here we are focusing on finding the middle element that acts as a reference frame whether to go left or right to it as the elements are already sorted. This searching helps in optimizing the search technique with every iteration is referred to as binary search and readers do stress over it as it is indirectly applied in solving questions.

Iteration method

    static int findIdx(int key, int a[]) {
        int n = a.length;
        int low = 0;
        int high = n - 1;

        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (a[mid] == key) {
                return mid;
            } else if (a[mid] > key) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }

        return -1;
    }

Recursion method

    static int binarySearch(int key, int[] a, int startIdx, int endIdx) {
        if (startIdx > endIdx) {
            return -1;
        }

        int mid = startIdx + (endIdx - startIdx) / 2;
        if (a[mid] == key) {
            return mid;
        }
        if (a[mid] > key) {
            return binarySearch(key, a, startIdx, mid - 1);
        }
        return binarySearch(key, a, mid + 1, endIdx);
    }

Key Points:

• Time Complexity : O(log n), where n is the number of elements in the array. This makes binary search very efficient for large datasets.

• Space Complexity : O(1) for iterative binary search, O(log n) for recursive binary search due to recursive calls on the stack.

• Sorted Data : Binary search works only on sorted data.

• Use Cases :

  • Searching for an element in a sorted array or list.
  • Finding the lower or upper bounds of elements.
  • Finding the square root, minimum/maximum in certain conditions.

• Basic

• Introduction to Java

• Array

• Time and Space Complexity

• Sorting

• String

• Recursion

• OOPs

• Linked List

---

Connect with me:

---