Java Binary Search
The following code implements the binary search algorithm. Its uses the Comparable interface to compare elements in the passed in array.
Another feature is that it uses the recursive in the implementation.
public class Main < public static final int NOT_FOUND = -1; public static int binarySearch(Comparable[] a, Comparable x) < return binarySearch(a, x, 0, a.length - 1); >//from w ww. j a v a 2s . com private static int binarySearch(Comparable[] a, Comparable x, int low, int high) < if (low > high) return NOT_FOUND; int mid = (low + high) / 2; if (a[mid].compareTo(x) < 0) return binarySearch(a, x, mid + 1, high); else if (a[mid].compareTo(x) > 0) return binarySearch(a, x, low, mid - 1); else return mid; > public static void main(String[] args) < int SIZE = 8; Comparable[] a = new Integer[SIZE]; for (int i = 0; i < SIZE; i++) a[i] = new Integer(i * 2); for (int i = 0; i < SIZE * 2; i++) System.out.println("Found " + i + " at " + binarySearch(a, new Integer(i))); > > The code above generates the following result.
Binary search without recursive
The following code uses the binary search algorithm to search a hard code array against hard coded value.
public class Main< public static void main(String[] args) < double[] x = < -39, -3, 6, 10, 4, 9, 10 >; // ww w .ja v a2 s . co m double value = 8; int lower = 0, upper = x.length - 1; while (lower int middle = (lower + upper) / 2; if (value > x[middle]) lower = middle + 1; else if (value < x[middle]) upper = middle - 1; else break; > if (lower > upper) System.out.println("Not found"); else System.out.println("Found"); > > The code above generates the following result.
Binary Search Insert
public class Main< public static void main(String[] args) < int maxSize = 100; BinarySearchArray arr = new BinarySearchArray(maxSize); arr.insert(2);//from w w w . j a v a 2 s . c o m arr.insert(0); arr.insert(5); arr.insert(6); arr.insert(4); arr.insert(9); arr.insert(4); arr.insert(7); arr.insert(5); arr.insert(9); arr.insert(8); arr.insert(2); arr.insert(4); arr.insert(6); arr.insert(8); arr.insert(9); arr.display(); // display array int searchKey = 27; // search for item if (arr.find(searchKey) != arr.size()) System.out.println("Found " + searchKey); else System.out.println("Can't find " + searchKey); > > class BinarySearchArray < private long[] a; private int nElems; public BinarySearchArray(int max) < a = new long[max]; // create array nElems = 0; > public int size() < return nElems; > public int find(long searchKey) < return recFind(searchKey, 0, nElems - 1); > private int recFind(long searchKey, int lowerBound, int upperBound) < int curIn; curIn = (lowerBound + upperBound) / 2; if (a[curIn] == searchKey) return curIn; // found it else if (lowerBound > upperBound) return nElems; // can't find it else // divide range < if (a[curIn] < searchKey) // in upper half return recFind(searchKey, curIn + 1, upperBound); else // in lower half return recFind(searchKey, lowerBound, curIn - 1); > > public void insert(long value) < int j; for (j = 0; j < nElems; j++) // find where it goes if (a[j] > value) // (linear search) break; for (int k = nElems; k > j; k--) // move bigger ones up a[k] = a[k - 1]; a[j] = value; // insert it nElems++; // increment size > public void display() < for (int j = 0; j < nElems; j++) System.out.print(a[j] + " "); System.out.println(""); > > The code above generates the following result.
0 2 2 4 4 4 5 5 6 6 7 8 8 9 9 9 Can't find 27 Next chapter.
What you will learn in the next chapter:
Java binary search insert
- Find the largest three distinct elements in an array
- Find Second largest element in an array
- Move all zeroes to end of array
- Rearrange array such that even positioned are greater than odd
- Rearrange an array in maximum minimum form using Two Pointer Technique
- Segregate even and odd numbers using Lomuto’s Partition Scheme
- Reversal algorithm for Array rotation
- Print left rotation of array in O(n) time and O(1) space
- Sort an array which contain 1 to n values
- Count the number of possible triangles
- Print All Distinct Elements of a given integer array
- Find the element that appears once in an array where every other element appears twice
- Leaders in an array
- Find Subarray with given sum | Set 1 (Non-negative Numbers)
- Rearrange an array such that arr[i] = i
- Rearrange positive and negative numbers in O(n) time and O(1) extra space
- Reorder an array according to given indexes
- Find the smallest missing number
- Difference Array | Range update query in O(1)
- Maximum profit by buying and selling a share at most twice
- Smallest subarray with sum greater than a given value
- Inversion count in Array using Merge Sort
- Merge two sorted arrays with O(1) extra space
- Majority Element
- Two Pointers Technique
- Find a triplet that sum to a given value
- Equilibrium index of an array
- MO’s Algorithm (Query Square Root Decomposition) | Set 1 (Introduction)
- Square Root (Sqrt) Decomposition Algorithm
- Sparse Table
- Range sum query using Sparse Table
- Range LCM Queries
- Minimum number of jumps to reach end
- Space optimization using bit manipulations
- Find maximum value of Sum( i*arr[i]) with only rotations on given array allowed
- Construct an array from its pair-sum array
- Maximum equilibrium sum in an array
- Smallest Difference Triplet from Three arrays
- Find the largest three distinct elements in an array
- Find Second largest element in an array
- Move all zeroes to end of array
- Rearrange array such that even positioned are greater than odd
- Rearrange an array in maximum minimum form using Two Pointer Technique
- Segregate even and odd numbers using Lomuto’s Partition Scheme
- Reversal algorithm for Array rotation
- Print left rotation of array in O(n) time and O(1) space
- Sort an array which contain 1 to n values
- Count the number of possible triangles
- Print All Distinct Elements of a given integer array
- Find the element that appears once in an array where every other element appears twice
- Leaders in an array
- Find Subarray with given sum | Set 1 (Non-negative Numbers)
- Rearrange an array such that arr[i] = i
- Rearrange positive and negative numbers in O(n) time and O(1) extra space
- Reorder an array according to given indexes
- Find the smallest missing number
- Difference Array | Range update query in O(1)
- Maximum profit by buying and selling a share at most twice
- Smallest subarray with sum greater than a given value
- Inversion count in Array using Merge Sort
- Merge two sorted arrays with O(1) extra space
- Majority Element
- Two Pointers Technique
- Find a triplet that sum to a given value
- Equilibrium index of an array
- MO’s Algorithm (Query Square Root Decomposition) | Set 1 (Introduction)
- Square Root (Sqrt) Decomposition Algorithm
- Sparse Table
- Range sum query using Sparse Table
- Range LCM Queries
- Minimum number of jumps to reach end
- Space optimization using bit manipulations
- Find maximum value of Sum( i*arr[i]) with only rotations on given array allowed
- Construct an array from its pair-sum array
- Maximum equilibrium sum in an array
- Smallest Difference Triplet from Three arrays
anizzomc / ArraySortedList.java
This example show how to implement using binary search as base algorithm to add elements to a sorted array list, keeping the array sorted. This method has O(Log N) complexity, because it «divides» the array by 2 each iteration to see where the element should go. If the element is repeated, this is placed next to it.
Belive or not, when you look on the internet how to insert an element to a sorted array, you will find this solution (BAD): void insert(array, element) < int pos; for(pos = 0 ; i < array.size() ; i++ ) < if(compare(array.get(pos), element) >0) < break; >> array.add(pos, element); >
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
| import java . util . ArrayList ; |
| import java . util . Comparator ; |
| import java . util . Iterator ; |
| public class ArraySortedList < T >implements SortedList < T > |
| private ArrayList < T >array ; |
| private Comparator < T >comparator ; |
| public ArraySortedList ( Comparator < T >comparator ) |
| array = new ArrayList < T >(); |
| assert comparator != null ; |
| this . comparator = comparator ; |
| > |
| /** |
| * Insert an eleemnt to the list keeping the list sorted. |
| * Using «binary search» to look for the right place. |
| */ |
| @ Override |
| public void add ( T e ) |
| int left , right , mid ; |
| left = 0 ; |
| right = array . size (); |
| while ( left < right ) |
| mid = ( left + right )/ 2 ; |
| int result = comparator . compare ( array . get ( mid ), e ); |
| if ( result > 0 ) < //If e is lower |
| right = mid ; |
| > else < //If e is higher |
| left = mid + 1 ; |
| > |
| > |
| array . add ( left , e ); |
| > |
| @ Override |
| public Iterator < T >iterator () |
| return new ListIterator (); |
| > |
| private class ListIterator implements Iterator < T > |
| private int index = 0 ; |
| @ Override |
| public boolean hasNext () |
| return index < array . size (); |
| > |
| @ Override |
| public T next () |
| return array . get ( index ++); |
| > |
| @ Override |
| public void remove () |
| throw new UnsupportedOperationException ( «Not supported» ); |
| > |
| > |
| > |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
| Belive or not, when you look on the internet how to insert an element to a sorted array, you will find this solution: |
| void insert(array, element) |
| int pos; |
| for(pos = 0 ; i < array.size() ; i++ ) |
| if(compare(array.get(pos), element) > 0) |
| break; |
| > |
| > |
| array.add(pos, element); |
| > |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
| import java . util . Comparator ; |
| import java . util . Random ; |
| public class Main |
| public static void main ( String [] args ) |
| SortedList < Integer >list = new ArraySortedList < Integer >( new Comparator < Integer >() |
| @ Override |
| public int compare ( Integer o1 , Integer o2 ) |
| return o1 . compareTo ( o2 ); |
| > |
| >); |
| Random r = new Random (); |
| for ( int i = 0 ; i < 10000 ; i ++) |
| list . add ( r . nextInt ()); |
| > |
| Integer previous = Integer . MIN_VALUE ; |
| for ( Integer integer : list ) |
| assert previous |
| previous = integer ; |
| System . out . println ( integer ); |
| > |
| > |
| > |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
| //Interface |
| public interface SortedList < T > |
| /** |
| * Inserts an element to the list keeping the list sorted. |
| */ |
| public void add ( T element ); |
| > |
Of course the time complexity of your method is still O(n)!
not because of the binary search but because of the array.add(int i, E element) since is needs to shift the subsequent elements, it is still O(n).
https://docs.oracle.com/javase/8/docs/api/java/util/ArrayList.html#add-int-E-
Easy fix, just use a LinkedList.
Edit: Yeah right, that was a dumb idea
If you had a LinkedList then you’d lose the random access capability and wouldn’t be able to perform binary search.
Footer
You can’t perform that action at this time.