Detailed explanation of the implementation method of half search in JS array search

This article mainly introduces the implementation method of half search in JSarraysearch, and analyzes the principle of javascript array half search algorithm in combination with specific examples. Implementation skills and related Notes, friends in need can refer to the following

The example of this article describes the half search implementation method of JS array search. Share it with everyone for your reference, the details are as follows:

1. Method principle:

When searching for a specific value value from a given sequence array arr When , the half search method does this:

1. Determine the starting point of the search range: starting point startIndex = 0, end point endIndex = arr.length - 1;

2. According to the starting point To determine an intermediate point middle = Math.floor((end point - starting point) / 2);

3. Under the premise of startIndex < endIndex, compare the size of arr[middle] and value:

(1) arr[middle] < value

Adjust the search range to the second half of the array, that is, startIndex = middle + 1, endIndex = arr.length -1;

(2) arr[middle] > value

Adjust the search range to the first half of the array, that is, startIndex = 0, endIndex = middle - 1;

Then, recalculate middle and compare again arr[middle] and value, until they are equal or startIndex >= endIndex.

2. Code:

// 该例的写法适用于序列为由小到大的数组
function binarySearch(arr, value) {
  var startIndex = 0,
  endIndex = arr.length - 1;
  middle = Math.floor((endIndex - startIndex) / 2);
  while (arr[middle] !== value && startIndex < endIndex) {
    if (arr[middle] > value) {
      endIndex = middle - 1;
    } else if (arr[middle] < value) {
      startIndex = middle + 1;
    }
    middle = Math.floor((endIndex - startIndex) / 2);
  }
  return (arr[middle] !== value) ? -1 : middle;
}

3. Advantages and disadvantages:

(1) Advantages:

Every time you search, the number of array items to be searched will be reduced by half, so its performance is better than the linear search method (when there are many array items , especially obvious);

(2) Disadvantages:

is only applicable to sequence arrays. Before using this method on ordinary arrays, the array needs to be sorted

The above is the detailed content of Detailed explanation of the implementation method of half search in JS array search. For more information, please follow other related articles on the PHP Chinese website!