Retrieval algorithm of javascript data structure and algorithm_javascript skills

There are two ways to find data, sequential search and binary search. Sequential search works on lists with randomly arranged elements. Binary search works on a sorted list of elements. Binary search is more efficient, but it must be a sorted set of list elements.

1: Sequential search
Sequential search is to judge the list elements one by one starting from the first element of the list until the desired result is found, or the desired element is not found until the end of the list.

The code is as follows:

function seqSearch(data,arr) {
  for(var i = 0; i < arr.length; ++i) {
    if(arr[i] == data) {
      return true;
    }
  }
  return false;
}

We can also return the sequential search function that matches the position of the element. The code is as follows:

function seqSearch(data,arr) {
  for(var i = 0; i < arr.length; ++i) {
    if(arr[i] == data) {
      return i;
    }
  }
  return -1;
}

Two: Find the minimum and maximum values

The algorithm for finding the minimum value in an array is as follows:

1. Assign the first element of the array to a variable and use this variable as the minimum value.
2. Start traversing the array, starting from the second element and comparing it with the current minimum value.
3. If the value of the current element is less than the current minimum value, set the current element to the new minimum value.
4. Move to the next element and repeat step 3.
5. When the program ends, what is stored in this variable is the minimum value.

The code is as follows:

function findMin(arr) {
  var min = arr[0];
  for(var i = 1; i < arr.length; ++i) {
    if(arr[i] < min) {
      min = arr[i];
    }
  }
  return min;
}

The algorithm for finding the maximum value is similar to the minimum value above. First, set the first element in the array to the maximum value, and then loop to compare each remaining element of the array with the current maximum value. If the value of the current element is greater than the current Maximum value, then assign the value of the element to the maximum value. The code is as follows:

function findMax(arr) {
  var max = arr[0];
  for(var i = 1; i < arr.length; ++i) {
    if(arr[i] > max) {
      max = arr[i];
    }
  }
  return max;
 }

Three: Binary search method.

If the data you are looking for is ordered, the binary search algorithm is more efficient than the sequential search algorithm. The basic principle of the binary search algorithm is as follows:

1. Set the first position of the array to the lower boundary (0).
2. Set the position of the last element of the array to the upper boundary (the length of the array minus 1).
3. If the lower boundary is equal to or smaller than the upper boundary, do the following:
A. Set the midpoint to (upper boundary plus lower boundary) divided by 2.
B. If the element at the midpoint is smaller than the query value, set the lower boundary to the subscript of the midpoint element plus 1.
C. If the element at the midpoint is greater than the query value, set the upper boundary to the subscript of the midpoint element minus 1.
D. Otherwise, the midpoint element is the data to be found and can be returned.

The code is as follows:

// 二分查找算法
function binSearch(data,arr) {
var lowerBound = 0;
  var upperBound = arr.length - 1;
  while(lowerBound <= upperBound) {
    var mid = Math.floor((upperBound + lowerBound)/2);
    if(arr[mid] < data) {
      lowerBound = mid + 1;
    }else if(arr[mid] > data) {
      upperBound = mid - 1;
    }else {
      return mid;
    }
  }
  return -1;
}
 // 快速排序
function qSort(list) {
  if(list.length == 0) {
    return [];
  }
  // 存储小于基准值的值
  var left = [];
  // 存储大于基准值的值
  var right = [];
  var pivot = list[0];
  for(var i = 1; i < list.length; i++) {
    if(list[i] < pivot) {
      left.push(list[i]);
    }else {
      right.push(list[i])
    }
  }
  return qSort(left).concat(pivot,qSort(right));
}
 // 测试代码
var numbers = [0,9,1,8,7,6,2,3,5,4];
var list = qSort(numbers);
console.log(binSearch(6,list));

4: Calculate the number of repetitions;
When the binary search algorithm binSearch() function finds a certain value, if there are other same values ​​in the data set, then the function will be positioned near similar values. In other words, other same values ​​may appear. The left or right side of the value found.

Then our simplest solution is to write two loops, one that simultaneously traverses the data set downward or to the left, counting the number of repetitions; and then, traversing upward or to the right, counting the number of repetitions. The code is as follows:

// 计算重复次数
function count(data,arr) {
  var count = 0;
  var arrs = [];
  var position = binSearch(data,arr);
  if(position > -1) {
    ++count;
    arrs.push({"index":count});
    for(var i = position -1; i > 0; --i) {
      if(arr[i] == data) {
        ++count;
        arrs.push({"index":count});
      }else {
        break;
      }
    }
    for(var i = position + 1; i < arr.length; ++i) {
      if(arr[i] == data) {
        ++count;
        arrs.push({"index":count});
      }else {
        break;
      }
    }
  }
  return arrs;
}
 // 测试重复次数的代码
var arr = [0,1,1,1,2,3,4,5,6,7,8,9];
var arrs = count(1,arr);
console.log(arrs);
console.log(arrs.length);

As shown below: