Binary search code java

Java Guides

In computer science, searching is the process of finding an item with specified properties from a collection of items. The items may be stored as records in a database, simple data elements in arrays, text in files, nodes in trees, vertices and edges in graphs, or they may be elements of other search spaces.

Why do we need Searching?

Searching is one of the core computer science algorithms. We know that today’s computers store a lot of information. To retrieve this information proficiently we need very efficient search algorithms.

There are certain ways of organizing the data that improve the searching process. That means, if we keep the data in proper order, it is easy to search for the required element. Sorting is one of the techniques for making the elements ordered. In this article, we will see different search algorithms.

Binary Search with Example

Binary search is a fast search algorithm with run-time complexity of Ο(log n). This search algorithm works on the principle of divide and conquer. For this algorithm to work properly, the data collection should be in the sorted form.

Let us consider the problem of searching for a word in a dictionary. Typically, we directly go to some approximate page [say, middle page] and start searching from that point. If the name that we are searching for is the same then the search is complete. If the page is before the selected pages then apply the same process for the first half; otherwise, apply the same process to the second half. Binary search also works in the same way. The algorithm applying such a strategy is referred to as a binary search algorithm.

How Binary Search Works?

For a binary search to work, it is mandatory for the target array to be sorted. We shall learn the process of binary search with a pictorial example.

The following is our sorted array and let us assume that we need to search the location of value 10 using binary search.

Now we compare the value stored at location 4, with the value being searched, i.e. 10. We find that the value at location 4 is 8, which is not a match. As the value is greater than 8 and we have a sorted array, so we also know that the target value must be in the upper portion of the array.

low = mid + 1 mid = low + (high - low) / 2 

The value stored at location 7 is not a match, rather it is more than what we are looking for. So, the value must be in the lower part from this location.

Binary Search Implementation using Java

Let’s write a source code for binary search in Java. There are many ways we can write logic for binary search:

1. Iterative implementation
2. Recursive Implementation
3. Using Arrays.binarySearch()
4. Using Collections.binarySearch()

Iterative Implementation

public class BinarySearch < public int binarySearchIteratively(int[] sortedArray, int key) < int low = 0; int high = sortedArray.length - 1; int index = Integer.MAX_VALUE; while (low  high) < int mid = (low + high) / 2; if (sortedArray[mid]  key) < low = mid + 1; > else if (sortedArray[mid] > key) < high = mid - 1; > else if (sortedArray[mid] == key) < index = mid; break; > > return index; > public static void main(String[] args) < int[] sortedArray = < 0, 1, 2, 3, 4, 5, 5, 6, 7, 8, 9, 9 >; int key = 6; BinarySearch binSearch = new BinarySearch(); int index = binSearch.binarySearchIteratively(sortedArray, key); System.out.println("Search element found " + key+ " in location index : " + index); > >

Search element 6 found in location index : 7 

The binarySearchIteratively method takes a sortedArray, key & the low & high indexes of the sortedArray as arguments. When the method runs for the first time the low, the first index of the sortedArray, is 0, while the high, the last index of the sortedArray, is equal to its length – 1.

The middle is the middle index of the sortedArray. Now the algorithm runs a while loop comparing the key with the array value of the middle index of the sortedArray.

Recursive Implementation

public class BinarySearch < public int binarySearchRecursively(int[] sortedArray, int key, int low, int high) < int middle = (low + high) / 2; if (high  low) < return -1; > if (key == sortedArray[middle]) < return middle; > else if (key  sortedArray[middle]) < return binarySearchRecursively(sortedArray, key, low, middle - 1); > else < return binarySearchRecursively(sortedArray, key, middle + 1, high); > > public static void main(String[] args) < int[] sortedArray = < 0, 1, 2, 3, 4, 5, 5, 6, 7, 8, 9, 9 >; int key = 6; BinarySearch binSearch = new BinarySearch(); int index = binSearch.binarySearchRecursively(sortedArray, key, 0, sortedArray.length -1); System.out.println("Search element found in location index : " + index); > >

Search element found in location index : 7 

The binarySearchRecursively method accepts a sortedArray, key, the low and high indexes of the sortedArray.

Using Arrays.binarySearch()

public class BinarySearch < public int runBinarySearchUsingJavaArrays(int[] sortedArray, Integer key) < int index = Arrays.binarySearch(sortedArray, key); return index; > public static void main(String[] args) < int[] sortedArray = < 0, 1, 2, 3, 4, 5, 5, 6, 7, 8, 9, 9 >; int key = 6; BinarySearch binSearch = new BinarySearch(); int index1 = binSearch.runBinarySearchUsingJavaArrays(sortedArray, key); System.out.println("Search element found in location index : " + index1); > >

Search element found in location index : 7

Using Collections.binarySearch()

public class BinarySearch < public int runBinarySearchUsingJavaCollections(ListInteger> sortedList, Integer key) < int index = Collections.binarySearch(sortedList, key); return index; > public static void main(String[] args) < Integer[] sortedArray = < 0, 1, 2, 3, 4, 5, 5, 6, 7, 8, 9, 9 >; int key = 6; BinarySearch binarySearch = new BinarySearch(); int index1 = binarySearch.runBinarySearchUsingJavaCollections(Arrays.asList(sortedArray), key); System.out.println("Search element found in location index : " + index1); > >

Search element found in location index : 7 

Auxiliary Space: O(1) in the case of iterative implementation. In the case of recursive implementation, O(Logn) recursion call stack space.

Источник

Бинарный поиск на Java

С одной стороны, для подобных алгоритмов используют уже готовые функции стандартной библиотеки, с другой – подобные вопросы на собеседованиях позволяют узнать полезное о кандидате.

Первое что приходи на ум: перебор элементов в массиве до нужного, тогда если количество элементов равно n и нужный нам элемент будет последним, нам потребуется сделать n проверок элементов до нахождения нужного, про такой случай и говорят что сложность алгоритма равна O(n).

Рассмотрим другой подход — бинарный поиск – возьмем средний элемент отсортированного массива и сравним его c искомым. Если элемент меньше – продолжим поиск в левой части массива, если больше в правой, пока не останется нужный элемент. Таким образом нам понадобится число операций равное тому, сколько раз нам нужно поделить массив размером n пополам.

Например, для массива в 16 элементов мы сначала поделим его на два по 8, потом 8 на два по 4, потом 4 на два по 2 и на конец 2 пополам, те всего 4 операции в худшем случае. Такое число равно двоичному логарифму.

Без рекурсии

public class Binary < public static void main(String[] args) < int[] values = ; int valueToFind = 3; System.out.printf("Index = %d%n", binarySearch(values, valueToFind, 0, values.length - 1)); > private static int binarySearch(int[] sortedArray, int valueToFind, int low, int high) < int index = -1; while (low else if (sortedArray[mid] > valueToFind) < high = mid - 1; >else if (sortedArray[mid] == valueToFind) < index = mid; break; >> return index; > >

С использованием рекурсии

public class Binary < public static void main(String[] args) < int[] values = ; int valueToFind = 3; System.out.printf("Index = %d%n", binarySearch(values, valueToFind, 0, values.length - 1)); > private static int binarySearch(int[] values, int valueToFind, int l, int r) < if (l == r) < return (values[l] == valueToFind) ? l : -1; >int m = l + (r - l) / 2; if (valueToFind > values[m]) < return binarySearch(values, valueToFind, m + 1, r); >else if (values[m] > valueToFind) < return binarySearch(values, valueToFind, l, m - 1); >return m; > >

Если элемент не найден, то вернется -1 .

Во многих примерах в интернете можно встретить запись int m = (l + r) / 2; , вместо int mid = l + (r — l) / 2; . И у меня в заметке тоже была такая запись, пока один из читателей не обратил на это внимание.

Но использование второго варианта является лучшей практикой, так как это помогает избежать переполнения, когда размер массива велик.

Например, если l = 2147483647 и r = 2147483647 , сумма l и r будет равна 4294967294, что превышает максимальное значение, которое может удерживать int , вызывая переполнение.

С другой стороны, если вы используете mid = l + (r — l) / 2; это будет работать, как и ожидалось, потому что вычитание будет сделано первым, а результат будет равен нулю, поэтому деление будет равно нулю, а сложение вернет значение l .

Источник

Binary Search in Java explained with examples

Binary search is used to find an element among many other elements. The binary search method is faster than the linear search method. The array members must be in ascending order for binary search. To get rid of the unsorted arrays, you can use the Arrays.sort(arr) method to sort it.

Java Linear Search

A simple strategy for searching is linear search. The array is scanned progressively in this method, and each element is compared to the key until the key is found or the array is reached.

• Using the iterative approach
• Using a recursive approach
• Using Arrays.binarySearch () method.

All three techniques will be implemented and discussed in this session.

Binary search algorithm in Java

The collection is repeatedly divided in half in the binary search technique. The main item is found in the collection’s left or right half based on whether the key is less than or greater than the collection’s mid element.

• Calculate the collection’s middle element.
• Compare and contrast the key elements with the central element.
• We return the central index position for the key discovered if the key Equals the middle element.
• Else If key > mid element, the key is located in the collection’s right half. As a result, repeat steps 1–3 on the collection’s lower (right) half.
• Otherwise, if the key is in the central element, the key is in the upper half of the collection.
• As a result, the binary search in the upper half must be repeated.

As you can see from the preceding stages, half of the elements in the collection are rejected after the first comparison in the Binary search. It’s worth noting that the identical techniques apply to both iterative and recursive binary searches. As a result, we divide the array several times and decide which half to search for the key by comparing the key element to the mid. Binary search is highly efficient as far as time and accuracy and is much faster.

Java Binary Search Implementation

Let’s use the strategy mentioned above to create a Binary search application in Java that uses an iterative approach. We use an example array in this program and do a binary search.

import java.util.*; class Codeunderscored < public static void main(String args[])< int numArray[] = ; System.out.println(" array input: " + Arrays.toString(numArray)); //relevant key to be searched int key = 35; System.out.println("\nSearched key=" + key); //set start_idx to the array's first index int start_idx = 0; //set end_idx to the last elements in array int end_idx=numArray.length-1; //calculate the array's mid_idx int mid_idx = ( start_idx + end_idx)/2; //as long as the first and last do not overlap while( start_idx else if ( numArray[mid_idx] == key )< //if key = element at central, then go ahead and print the location System.out.println("Item found at index: " + mid_idx); break; >else < // search for the key in the array's second half end_idx = mid_idx - 1; >mid = ( start_idx + end_idx)/2; > //if start_idx and end_idx overlap, then key is not present in the array if ( start_idx > end_idx ) < System.out.println("Item not found!"); >> >

The given program demonstrates an iterative Binary search method. An array is declared first, followed by a key to be searched. After determining the array’s central element, the key is compared to the central element. The key is then searched in the lower or upper half of the array based on whether it is less than or greater than the key.

Performing Recursive binary search in Java

You can also use the recursion approach to execute a binary search. The binary search strategy is used here recursively until the key is located or the list is exhausted.

The following is the program that implements a recursive binary search:

import java.util.*; class Codeunderscored< // binary search via recursive approach public static int binary_Search(int intArray[], int start_idx, int end_idx, int key)< // If the array is in order, execute a binary search on it. if (end_idx>=start_idx) < //calculate mid int mid_idx = start_idx + (end_idx - start_idx)/2; //if key =intArray[mid_idx] return mid_idx if (intArray[mid_idx] == key)< return mid_idx; >//if intArray[mid_idx] > key then key is in left half of array if (intArray[mid_idx] > key)< return binary_Search(intArray, start_idx, mid-1, key);// searching for the key recursively >else //key is present in the array's right half < return binary_Search(intArray, mid_idx+1, end_idx, key);//recursively search for key >> return -1; > public static void main(String args[])< // array and key definition int intArray[] = ; System.out.println("Input List: " + Arrays.toString(intArray)); int key = 31; System.out.println("\nThe key we are looking for is:" + key); int end_idx=intArray.length-1; //calling the binary search method int result = binary_Search(intArray,0,end_idx,key); //printing the result if (result == -1) System.out.println("\nKey is not available in the provided list!"); else System.out.println("\nKey is available at position: "+result + " in the list"); > >

Using Arrays.binarySearch () function

The Arrays class in Java includes a ‘binarySearch ()’ method that executes the binary search on the provided array. The given array and the key to be searched are sent as parameters, and the position of the key in the array is returned. The method returns -1 if the key cannot be found.

The Arrays.binarySearch () method is implemented in the example below.

import java.util.Arrays; class Codeunderscored< public static void main(String args[])< // array definition int intArray[] = ; System.out.println(" Array input is : " + Arrays.toString(intArray)); //establish the key we want to search for int key = 60; System.out.println("\nThe key we are looking for is:" + key); //calling the binarySearch method on the provided array given the key to be searched int result = Arrays.binarySearch(intArray,key); //printing the return result if (result < 0) System.out.println("\nKey is not available in the provided array!"); else System.out.println("\nKey is available at index: "+result + " in the array."); >>

Java Iterative Binary Search Example

Let’s look at a binary search example in Java.

class BinarySearchExample < public static void binarySearch(int arr[], int first, int last, int key)< int mid_idx = (start_idx + end_idx)/2; while( start_idx else if ( arr[mid_idx] == key )< System.out.println("Element is available at the index: " + mid_idx); break; >else < end_idx = mid_idx - 1; >mid_idx = (first_idx + last_idx)/2; > if ( first_idx > last_idx ) < System.out.println("Element is not available!"); >> public static void main(String args[])< int arr[] = ; int key = 40; int end_idx=arr.length-1; binarySearch(arr,0,end_idx,key); > >

Example of a Binary Search in Java with Recursion

Let’s look at an example of binary search in Java, where we’ll use recursion to find an element from an array.

Источник