Skip to main content

Binary Search Tree

A prerequisite to doing a binary search is that the list we are searching from is SORTED otherwise it wouldn't work as we expected. A key concept of binary search is in contrast to linear search, we divide the set of choices we have into halves and checking whether whatever we are looking for is in the upper half or lower half of the divided set.

For Example:​

int search\[\] ={1,22,33,44,56,67,78,89,90,101};  And we are looking for any number, say 78.

How it works​

First we get the middle of the array, and check whether what we are searching for is in the lower half or bigger half. After decide which half our search value is located, we discard the half that we no longer need and continue dividing it in half and looking for the search value.

Inputs

  • search - the array to search in
  • findMe - the value we are for in search Array

Outputs Index position where a[i] == x or-1 if not found

Implementation:​

public static void main(String\[\]args){  
        int search\[\]={1,22,33,44,56,67,78,89,90,101};  
        System.out.println(binarySearch(search,22));  
 }  
  
public static int binarySearch(int\[\]search,int findMe){  
        int tail=0;  
        int head=search.length-1;  
 while(tail<=head){  
        int halfway=(tail+head)/2; //Notes#1  
         if(search\[halfway\]==findMe){    //Notes#2  
         return halfway;  
         }else if(search\[halfway\]>findMe){  //Notes#3  
         head=halfway-1;  
         }else{     //Notes#4  
         tail=halfway+1;  
         }  
       }  
    return\-1;  
 }

Notes:​

  1. To get halfway of the array we can add tail and head and divide it by 2. 
  2. if we find it is already the value return the index
  3. if we find that our search value is less than the halfway point discard the bigger half
  4. By updating the head as halfway of the array -1, once the while loop triggers again, the new halfway will be starting on the lower half of the array and so on
  5. else if we find that our search value is greater than halfway point discard the lower half

Efficiency of Algorithm​

O(log n)