Binary search

Introduction

Binary search compares the key element to the middle element of the array,
If they are not equal, the half in which the key element cannot lie is eliminated and the search continues on the remaining half, again taking the middle element to compare to the key element, and repeating this until the key element is found,
If the search ends with the remaining half being empty, the key element is not in the array,

Performance:
Binary Search Algorithm is a very commonly used searching algorithm. Because it’s very efficient in searching. It always works on the sorted array.

Source code:

function binarySearchJavaScript(array, keyElement)
{
    var lowerBound  = 0,
        upperBound   = array.length - 1,
        midValue = Math.floor((upperBound + lowerBound)/2);

    while(array[midValue] != keyElement && lowerBound < upperBound)
    {
       if (keyElement < array[midValue]) { upperBound = midValue - 1; } else if (keyElement > array[midValue])
        {
            lowerBound = midValue + 1;
        }

        midValue = Math.floor((upperBound + lowerBound)/2);
    }

    return (array[midValue] != keyElement) ? "Key element "+keyElement+" not found " : "Key element "+ keyElement +" found at position "+ midValue;
}

var array = [1, 2, 3, 4, 5, 7, 8, 9];
array.sort();
console.log(binarySearchJavaScript(array, 1));   
console.log(binarySearchJavaScript(array, 5));
console.log(binarySearchJavaScript(array, 10));
// output
// Key element 1 found at position 0
// Key element 5 found at position 4
// Key element 10 not found

function binarySearchPHP($array, $keyElement) 
{ 
    if (count($array) === 0) return false; 
    $lowerBound = 0; 
    $upperBound = count($array)-1; 
      
    while ($lowerBound <= $upperBound) { 
          
        $middleValue = floor(($lowerBound + $upperBound) / 2); 
   
        if($array[$middleValue] === $keyElement) { 
            return "$keyElement found at position ".$array[$middleValue]."\n"; 
        } 
  
        if ($keyElement &lt; $array[$middleValue]) { 
            $upperBound = $middleValue -1; 
        } 
        else { 
            $lowerBound = $middleValue + 1; 
        } 
    } 
      
    return "$keyElement not found...\n"; 
} 
  
$array = array(1, 2, 3, 4, 5,6,7,8,9,10); 
echo binarySearchPHP($array,2); 
echo binarySearchPHP($array,5); 
echo binarySearchPHP($array,11); 

// output
// 2 found at position 2
// 5 found at position 5
// 11 not found...

def binarySearchPython(item_list,item):
    lowerBound = 0
    upperBound = len(item_list)-1
    isFound = False
    while( lowerBound<=upperBound and not isFound):
        midValue = (lowerBound + upperBound)//2
        if item_list[midValue] == item :
            isFound = True
        else:
            if item &lt; item_list[midValue]:
                upperBound = midValue - 1
            else:
                lowerBound = midValue + 1    
    return isFound
    
print(binarySearchPython([1,2,3,5,8], 6))
print(binarySearchPython([1,2,3,5,8], 5))

Also, read What is Linear search?

Binary search

Binary search

2 thoughts on “Binary search”