This is the thirteenth day of my participation in the August More Text Challenge. For details, see “August More Text Challenge”.

Everybody is good, we talked about the previous chapters bubbling, select, insert, merge and quick sort, understand some of the more familiar sorting algorithms, we going to talk about today is sequence and the binary search, two search algorithms, after understanding to our actual work still very useful, then let’s have a look at these two search algorithm!!!!

Sequential search

It’s a very inefficient algorithm, but it’s great for getting started,

The idea of sequential search

  • Go through the group.

  • If it finds an element equal to the target, it returns its index.

  • At the end of the walk, if no target value has been found, -1 is returned.

implementation

Array.prototype.sequentialSearch = function (item) {
    for (let i = 0; i < this.length; i++) {
        if (this[i] === item) {
            return i
        }
    }
    return -1
}

const res = [1.2.3.4.5]
console.log(res.sequentialSearch(3));
console.log(res.sequentialSearch(6));
/ / 2 to 1
Copy the code

Time complexity of sequential search

  • Traversing the array is a loop operation.

  • Time complexity: O(n).

Binary search

Binary search, also known as binary search, is an algorithm that searches for a particular element in an ordered array. It is much more efficient than sequential search because each search is halved without having to go through each element as sequential search does.

Binary search

  • Start with the middle element of the array, and if that middle element happens to be the target value, the search ends.

  • If the target value is greater or less than the middle element, the half of the array that is greater or less than the middle element is searched.

  • If the target value is not found at the end of the search, -1 is returned.

implementation

Array.prototype.binarySearch = function (item) {
    let low = 0
    let high = this.length - 1
    while (low <= high) {
        const mid = Math.floor((low + high) / 2)
        const element = this[mid]
        if (element < item) {
            low = mid + 1
        } else if(element > item) {
            high = mid - 1
        } else {
            return mid
        }
    }
    return -1
}

const res = [1.2.3.4.5]
console.log(res.binarySearch(3));
console.log(res.binarySearch(6));
/ / 2 to 1
Copy the code

Time complexity of binary search

  • Each comparison Narrows the search area by half.

  • Time complexity: O(logN).

End~~~