Anonymous user
Binary search: Difference between revisions
→[[Java]]: Added recursive implementation.
(→[[Java]]: Added recursive implementation.) |
|||
Line 31:
}
==
[[Category: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);
}
...
==Recursive==
public static int binarySearch(int[] nums, int check, int lo, int hi){
if(hi < lo){
return -1;
}
int guess = (hi + lo) / 2;
if(nums[guess] > check){
return binarySearch(nums, check, lo, guess - 1);
}else if(nums[guess]<check){
return binarySearch(nums, check, guess + 1, hi);
}
return guess;
}
| |||