binary search

Catalog

Binary search

Introduce dichotomy search

The search idea of dichotomy

Examples of dichotomy

Their thinking

Code implementation

Binary search

Introduce dichotomy search

Binary search , Also known as the half method , It's a kind of In an ordered array Search algorithm for finding specific elements .

Time complexity ：

The worst-case finding result is the last element （ Or the first element ）T(n)=T(n/2)+O(1) therefore T(n)=O(log2n)

The best situation O(1) The element to be found is the intermediate element （ The middle of an odd length sequence , The middle left element of an even length sequence ）

Spatial complexity      S(n)=logn

The search idea of dichotomy

1、 First , Search from the middle of the array , If the element happens to be the target element , Then the search process is over , Otherwise go to the next step .

2、 If the target element is greater than / Less than middle element , Then the array is larger than / Less than that half of the middle element to find , Then repeat step 1 , Do a recursive search .

3、 If a step array is empty , The target element cannot be found .

Examples of dichotomy

Their thinking

for example , In ordered data [26,30,45,55,60,61,62,65,70,78,99]  Search for 55 The process of

Code implementation

It should be noted that ： Before using dichotomy, sort the array , Dichotomy is for ordered arrays .

non-recursive algorithm

function binarySearch(arr,key){
    var low=0; // Array minimum index value 
    var high=arr.length-1; // Array maximum index value 
    while(low<=high){
        var mid=Math.floor((low+high)/2);
        if(key==arr[mid]){
            return mid;
        }else if(key>arr[mid]){
            low=mid+1;
        }else{
            high=mid-1;
        }
    }
    return -1;  //low>high The situation of , In this case key The value is greater than arr The largest element value in or key The value is less than arr Minimum element value in 
}

Achieve results

A recursive algorithm  

function binarySearch(arr,low,high,key){
    if(low>high){
      return -1;
    }
    var mid=Math.floor((low+high)/2);
    if(key==arr[mid]){
        return mid;
    }else if(key<arr[mid]){
        high=mid-1;
        return binarySearch(arr,low,high,key);
    }else{
        low=mid+1;
        return binarySearch(arr,low,high,key);
    
    }   

  Achieve results