{"id":11072,"date":"2022-12-15T09:50:33","date_gmt":"2022-12-15T09:50:33","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=11072"},"modified":"2023-04-18T13:33:28","modified_gmt":"2023-04-18T13:33:28","slug":"binary-search-program-in-java","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/binary-search-program-in-java\/","title":{"rendered":"Binary Search Program in Java"},"content":{"rendered":"

\"\"<\/p>\n

Searching is one of the most fundamental operations in computer science. It involves finding a specific element from a given data set. There are several search algorithms available, and one of the most efficient and widely used algorithms is the Binary search algorithm. In this article, we will discuss Binary Search in Java, its logic, and its implementation.<\/p>\n

The Logic of Binary Search in Java<\/h2>\n

The logic of binary search in Java is to search for an element in a sorted array by repeatedly dividing the search interval in half. The algorithm starts by comparing the element to be searched with the middle element of the array. If the element matches the middle element, the search is successful, and the index of the middle element is returned.<\/p>\n

If the element is less than the middle element, the search is continued in the left half of the array, as the element can only be present in that half. If the element is greater than the middle element, the search is continued in the right half of the array, as the element can only be present in that half.<\/p>\n

The search interval is again divided in half, and the process continues until the element is found or until the search interval becomes empty.<\/p>\n

The key idea behind binary search is to reduce the search space by half at every step of the algorithm. This reduces the number of comparisons required to find the element, making the search more efficient. The time complexity of the binary search is O(log n), where n is the number of elements in the array.<\/p>\n

Binary Search in Java Explanation<\/h2>\n

Item to be searched=20
\ninput:<\/p>\n\n\n\n\n\n
0<\/th>\n1<\/th>\n2<\/th>\n3<\/th>\n4<\/th>\n<\/tr>\n<\/thead>\n
10<\/td>\n11<\/td>\n16<\/td>\n20<\/td>\n23<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

beg=0, end=4, mid=2<\/p>\n\n\n\n\n\n
0<\/th>\n1<\/th>\n2<\/th>\n3<\/th>\n4<\/th>\n<\/tr>\n<\/thead>\n
10<\/td>\n11<\/td>\n16<\/td>\n20<\/td>\n23<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

beg=3, end=4, mid=3<\/p>\n\n\n\n\n\n
0<\/th>\n1<\/th>\n2<\/th>\n3<\/th>\n4<\/th>\n<\/tr>\n<\/thead>\n
10<\/td>\n11<\/td>\n16<\/td>\n20<\/td>\n23<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

Element found at index 3, Hence 3 will get returned.<\/p>\n

Algorithm of Binary search in Java<\/h2>\n

The general steps for both methods (iterative and recursive) are discussed below:<\/p>\n

    \n
  • Step 1<\/strong> – Read the user\u2019s search element.<\/li>\n
  • Step 2<\/strong> – Initialize the lower and upper bounds of the search interval. For the iterative method, this is done using two variables l and r, whereas, for the recursive method, this is done by passing the bounds as arguments to the function.<\/li>\n
  • Step 3<\/strong> – Find the middle element of the search interval by calculating the average of the lower and upper bounds. For the iterative method, this is done using the formula m = l + (r – l) \/ 2, whereas for the recursive method, this is done inside the function by calculating mid = l + (r – l) \/ 2.<\/li>\n
  • Step 4<\/strong> – Compare the middle element with the element to be searched. If they are equal, return the index of the middle element.<\/li>\n
  • Step 5<\/strong> – If the element is less than the middle element, then the search continues in the left half of the array. For the iterative method, this is done by updating the upper bound to r = m – 1, whereas, for the recursive method, this is done by making a recursive call to the function with the same lower bound and a new upper bound of m – 1.<\/li>\n
  • Step 6<\/strong> – If the element is greater than the middle element, then the search continues in the right half of the array. For the iterative method, this is done by updating the lower bound to l = m + 1, whereas, for the recursive method, this is done by making a recursive call to the function with the same upper bound and a new lower bound of m + 1.<\/li>\n
  • Step 7<\/strong> – Repeat steps 3-6 until the element is found or the search interval is empty.<\/li>\n
  • Step 8<\/strong> – If the element is not found in the array, return -1 and display "Element is not found in the array!!!".<\/li>\n<\/ul>\n

    Pseudo Code for Both the Logics (Recursive and Iterative)<\/h2>\n

    Iteration Method of Binary Search in Java<\/strong>
    \ndo until the pointers low and high meet each other.<\/p>\n

        mid = (low + high)\/2\n    if (x == arr[mid])\n        return mid\n    else if (x > arr[mid]) \/\/ x is on the right side\n        low = mid + 1\n    else                       \/\/ x is on the left side\n        high = mid - 1<\/code><\/pre>\n
    Recursive Method of Binary Search in Java<\/strong>
    \nbinarySearch(arr, x, low, high)<\/p>\n
        if high >= low\n        mid = (low + high) \/ 2 \n        if x == arr[mid]\n            return mid\n        else if x > arr[mid]        \/\/ x is on the right side\n            return binarySearch(arr, x, mid + 1, high)\n        else                               \/\/ x is on the right side\n            return binarySearch(arr, x, low, mid - 1)\n    return -1<\/code><\/pre>\n
    Program for Binary Search in Java Using Recursive Approach<\/h2>\n
    Below is the code implementation and explanation of the program for Binary Search in Java using the recursive approach:<\/p>\n\t\t\t\t\t\t