Binary Search
Binary search relies on a divide and conquer strategy to find a value
within an already-sorted collection. The algorithm is deceptively
simple. Pretend I was thinking of a number between 1 and 100. Every
guess you take, I'll say higher or lower. The most efficient way to
discover my number is to first guess 50. Higher. 75. Lower. 62. Higher
68. Yes!
Implementation
function findIndex(values, target) {
return binarySearch(values, target, 0, values.length - 1);
};
function binarySearch(values, target, start, end) {
if (start > end) { return -1; }
var middle = Math.floor((start + end) / 2);
var value = values[middle];
if (value > target) { return binarySearch(values, target, start, middle-1); }
if (value < target) { return binarySearch(values, target, middle+1, end); }
return middle;
}
findIndex([1, 4, 6, 7, 12, 13, 15, 18, 19, 20, 22, 24], 20);
---------------------in Java--------------------------
import java.util.Arrays;
public class test{
public static int bSearch(int[] arr, int key)
{
Arrays.sort(arr);
int low=0;
int high = arr.length;
while(low<=high)
{
int mid = (low+high)/2;
if(arr[mid]<key)
low = mid+1;
else if(arr[mid]>key)
high = mid - 1;
else
return arr[mid];
}
return 0;
}
public static void main(String args[])
{
int[] arr = {2,5,3,1,13,12,45};
int key = 15;
int n = arr.length;
System.out.println(bSearch(arr,key));
}
}
Linear Search
A linear search is the most basic of search algorithm you can have. A
linear search sequentially moves through your collection (or data
structure) looking for a matching value.
Implementation
function findIndex(values, target) {
for(var i = 0; i < values.length; ++i){
if (values[i] == target) { return i; }
}
return -1;
}
findIndex([7, 3, 6, 1, 0], 6)
0 Comments