Binary Search

swagasoft _binanry_search

Binary search is an efficient algorithm for finding an item from a sorted list of items. It works by iteratively splitting it into two parts of the list that may contain a targeted search until you reduce the possible location to one.

One of the most common ways to use binary search is to find an item in an array. Binary search is having a run-time complexity of O(log2 N).

A binary search begins by comparing the item in the center of the list with the target item. If the target value matches the center element, the position in the list is returned. If they do not match, the list is split in two. The first half consists of the first element to the middle element, and the second half consists of the elements from the middle element to the last element.

Binary Search Implementation Steps

  1. define the minimum value of your search which is zero.
  2. Find the maximum value from your list which is the length of the list – 1.
  3. If the maximum value is less than min we should stop the program because the target is not present in the list and return -1.
  4. Find the average of maximum value and minimum value and round it up to an integer.
  5. If the list[average] is equal to the target, we should stop the program and return the average.
  6. If the average was too low, that is list[average] < target, the set the minimum = average + 1.
  7. Otherwise set the maximum = average – 1.

binary search algorithm example

Find 73 in a list of [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 
		41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97];

const binarySearch = (array, target)=> {


}

 

  • defines the minimum value of your search which is zero.

 

Find 73 in a list of [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 
		41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97];

const binarySearch = (array, target)=> {
let min = 0;


}

 

  • Find the maximum value from your list which is the length of the list – 1.

 


let max = array.length - 1;

 

  • Find the average of maximum value and minimum value and round it up to an integer.

 


let average = Math.floor((max + min) / 2);

 

  • If the list[average] is equal to the target, we should stop the program and return the average.

 



while(min <= max){
if(array[average] === target){
return average;
}
}

 

  • If the average was too low, that is the list[average] < target, the set the minimum = average + 1.

 

 }else if(array[average] < target){
         min = average + 1;   
        }

 

  • Otherwise set the maximum = average – 1.

 

else{
       max = average - 1;
    }

Below is the complete code

//Find 73 in a list of [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 
		//41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97];

const binarySearch = (array, target)=> {
let min = 0;let max = array.length - 1;
let average;

   while (min <= max){average = Math.floor((max + min) / 2)
        if(array[average] === target){
         returnaverage;   
        }else if(array[average] < target){
         min =average + 1;   
        }else{
            max =average - 1;
    }
    
}
return -1;
}

let list =[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 
		41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97];

var result =binarySearch(list, 73);
console.log(result)

Another example



const binarySearch = (arr, target)=> {

    let start = 0;
    let end  = arr.length - 1;
    let middle  =   Math.floor((start +  end) / 2);
    let loop  = 0;

    while(arr[middle] !== target && start <= end){
        loop += 1;
        if(target < arr[middle]){
            end =  middle  - 1;
        }else{
            start =  middle + 1;
        }
        middle  =  Math.floor((start +  end) / 2);
    }

    return arr[middle] === target ? middle  : -1;

}

console.log(binarySearch([1,3,4,5,7,8,9,10,12,13,14,15], 14));

The run time complexity of this algorithm isO(log2 N).

Leave a Reply

Your email address will not be published. Required fields are marked *