Searching Algorithm

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; } //does not exist

  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; //found!
}
findIndex([1, 4, 6, 7, 12, 13, 15, 18, 19, 20, 22, 24], 20);
//finished 

 ---------------------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)