Last active
December 11, 2019 12:45
-
-
Save danielpinto8zz6/6d470eafa1d69b3faa5cf9775b9288e1 to your computer and use it in GitHub Desktop.
Binary search in java
This file contains hidden or 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
| /** | |
| * @param array A sorted array of ints to search through. This must be sorted. | |
| * @param key an int to seach the array for | |
| * @param start position where the arrays starts | |
| * @param end position where the array ends | |
| * @return wheter the key exists in the array | |
| */ | |
| public static boolean binarySearchRecursive(int[] array, int key, int start, int end) { | |
| int middle = (start + end) / 2; | |
| if (end < start) { | |
| return false; | |
| } | |
| if (key < array[middle]) { | |
| return binarySearchRecursive(array, key, start, middle - 1); | |
| } else if (key > array[middle]) { | |
| return binarySearchRecursive(array, key, middle + 1, end); | |
| } else if (key == array[middle]) { | |
| return true; | |
| } | |
| return false; | |
| } | |
| /** | |
| * @param array A sorted array of ints to search through. This must be sorted. | |
| * @param key an int to seach the array for | |
| * @return wheter the key exists in the array | |
| */ | |
| public static boolean binarySearchIterative(int[] array, int key) { | |
| int start = 0; | |
| int end = array.length - 1; | |
| while (start <= end) { | |
| int middle = (start + end) / 2; | |
| if (key < array[middle]) { | |
| end = middle - 1; | |
| } else if (key > array[middle]) { | |
| start = middle + 1; | |
| } else if (key == array[middle]) { | |
| return true; | |
| } | |
| } | |
| return false; | |
| } | |
| public static void main(String[] args) { | |
| int[] array = { 1, 8, 34, 67, 9, 6, 78, 12, 56, 41, 90 }; | |
| int key1 = 12, key2 = 91; | |
| Arrays.sort(array); | |
| System.out.println("Array :"); | |
| System.out.println(Arrays.toString(array)); | |
| System.out.println(); | |
| System.out.println("Using binary search iterative : "); | |
| System.out.println(binarySearchIterative(array, key1) ? key1 + " Found" : key1 + " Not found"); | |
| System.out.println(binarySearchIterative(array, key2) ? key2 + " Found" : key2 + " Not found"); | |
| System.out.println(); | |
| System.out.println("Using binary search recursive : "); | |
| System.out.println( | |
| binarySearchRecursive(array, key1, 0, array.length - 1) ? key1 + " Found" : key1 + " Not found"); | |
| System.out.println( | |
| binarySearchRecursive(array, key2, 0, array.length - 1) ? key2 + " Found" : key2 + " Not found"); | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment