Before explaining the binary search, let's first look at the linear search. How does linear search work? Using linear search, you traverse each element in an array and compare it with the key value to search for a value. Here is an example of a linear search.

Approach 1

Linear Search

For an array with a size of 9, the value at the 6th index must be found by searching from the starting index.
What about an array of a size N?
In the worst case

Complexity Graph for Linear Search

Javascript Code Samples

Linear Search Recursive Approach

function  getElement(arr, pointer, key,size){

      if(pointer > size){
          return false;
      }

     if(arr[pointer] === key ){
            return pointer;
     }

    return getElement(arr,pointer+1,key,size)
}

const arr = [1,10,15,20,25,30,40,50,100]
const result = getElement(arr,0,40,arr.length);
console.log(result);

Linear Search Iterative Approach

function  getIndex(arr, key){

    for (let i = 0; i < arr.length;  i++) {

        if(arr[i] == key){
            return i;
          };   
       }

    return false;
}


const arr = [1,10,15,20,25,30,40,50,100]
const result = getIndex(arr,40);
console.log(result);

Now let's take a look at Binary Search, which is much more efficient than regular search

Approach 2

Binary Search

Stage 1

Stage 2

Analysis

The final answer is obtained without traversing through all array elements.

Javascript Code

Iterative Approach

function searchValue(arr,key,low,high){

    while(low<=high){

        //calculates the middle index
        let  mid = Math.floor(low + ((high - low) /2))

        if( key === arr[mid] ){
             return mid;
        }
        if( key < arr[mid] ){
            high = mid-1;
        } 
        if( key > arr[mid] ){
            low = mid+1;
        }
    }
return -1;
}

const arr =[1,10,15,20,25,30,40,50,100]
const result = searchValue(arr,40,0,arr.length-1)
console.log(result)

Recursive Approach

function searchkey(arr,key,low,high){

    let mid = Math.floor(low + ((high - low)/2));

    if( key === arr[mid] ){ 
        return mid;
    }
    if( key < arr[mid] ){
        return searchkey(arr,key,low,mid-1);
    }
    if( key > arr[mid] ){
        return searchkey(arr,key,mid+1,high);
    }
    return -1;
}

const arr =[1,10,15,20,25,30,40,50,100]
const result = searchkey(arr,40,0,arr.length)
console.log(result);

Time Complexity

We only go to one of the recursive functions here, either the first recursive call or the second recursive call.

Recurrence Relation

Applying Master's Theorem

Complexity Chat

Happy Learning