Binary search: Difference between revisions
Content added Content deleted
(Added description and iterative Java implementation...working on recursive.) |
m (Fixed the algorithm definitions.) |
||
Line 1: | Line 1: | ||
Do a binary search through a sorted integer array for a certain number. Implementations can be recursive or iterative (both if you can). Print out whether or not the number was in the array afterwards. If it was, print the index also. The algorithms are as such (from [http://en.wikipedia.org/wiki/Binary_search the wikipedia]): |
Do a binary search through a sorted integer array for a certain number. Implementations can be recursive or iterative (both if you can). Print out whether or not the number was in the array afterwards. If it was, print the index also. The algorithms are as such (from [http://en.wikipedia.org/wiki/Binary_search the wikipedia]): |
||
Recursive: |
|||
BinarySearch(A[0..N-1], value, low, high) { |
BinarySearch(A[0..N-1], value, low, high) { |
||
if (high < low) |
if (high < low) |
||
Line 14: | Line 14: | ||
} |
} |
||
Iterative: |
|||
BinarySearch(A[0..N-1], value) { |
BinarySearch(A[0..N-1], value) { |
||
low = 0 |
low = 0 |
Revision as of 06:39, 8 November 2007
Do a binary search through a sorted integer array for a certain number. Implementations can be recursive or iterative (both if you can). Print out whether or not the number was in the array afterwards. If it was, print the index also. The algorithms are as such (from the wikipedia):
Recursive:
BinarySearch(A[0..N-1], value, low, high) { if (high < low) return not_found mid = (low + high) / 2 if (A[mid] > value) return BinarySearch(A, value, low, mid-1) else if (A[mid] < value) return BinarySearch(A, value, mid+1, high) else return mid }
Iterative:
BinarySearch(A[0..N-1], value) { low = 0 high = N - 1 while (low <= high) { mid = (low + high) / 2 if (A[mid] > value) high = mid - 1 else if (A[mid] < value) low = mid + 1 else return mid } return not_found }
Java
Iterative
... //check will be the number we are looking for //nums will be the array we are searching through int hi = nums.length - 1; int lo = 0; int guess = (hi + lo) / 2; while((nums[guess] != check) && (hi > lo)){ if(nums[guess] > check){ hi = guess - 1; }else if(nums[guess] < check){ lo = guess + 1; } guess = (hi + lo) / 2; } if(hi < lo){ System.out.println(check + " not in array"); }else{ System.out.println("found " + nums[guess] + " at index " + guess); } ...