Binary Search
Recursive
Recursive
public static int binarySearch(int[] a, int target, int min, int max) { if (min > max) { return -1; } // calculate the midpoint for roughly equal partition int mid = (min + max) / 2; if (mid >= a.length) { // Target is greater than the greatest number in the array. return -1; } // determine which subarray to search if (a[mid] < target) { // change min index to search upper subarray return binarySearch(a, target, mid + 1, max); } else if (a[mid] > target) { // change max index to search lower subarray return binarySearch(a, target, min, mid - 1); } else { // target found at index mid return mid; } }Iteration
public static int binarySearch(int a[], int target, int min, int max) { // continue searching while [min, max] is not empty while (max >= min) { // calculate the midpoint for roughly equal partition int mid = (max + min) / 2; if (mid >= a.length) { break; } // determine which subarray to search if (a[mid] < target) { // change min index to search upper subarray min = mid + 1; } else if (a[mid] > target) { // change max index to search lower subarray max = mid - 1; } else { // target found at index mid return mid; } } // target not found return -1; }
No comments:
Post a Comment