LinkMingle.com » 3 Versions of the Binary Search Algorithm

3 Versions of the Binary Search Algorithm

2
Votes

3 Versions of the famous Binary Search Algorithm

Binary Search for Searching an element in a sorted Array

This is the most common version of the Binary Search, where lower limit is set to middle+1 or higher limit to middle-1.

  
    int findBST(int[] inp,int val){
      int hi=inp.length-1; int lo = 0;
      while(lo<=hi){
       int mid = lo + (hi-lo)/2;
       if (inp[mid] == val)
            return mid;            
       else if(inp[mid] < val ) 
            lo = mid+1;
       else
            hi = mid-1;
      }
      return -1;
    }

Binary Search for finding the closest smaller element in case of its absence

Following changes are made from the normal BST.

Here we changed setting of lower limit to
```
    
	else if(inp[mid] < val ) 
            lo = mid;
```
as we are looking for the value smaller than val.
(hi-lo)>1 condition is added to the where clause as in this case there is a chance of infinite looping when the block size is 2.

    int findFirstSmallerBST(int[] inp,int val){
      if(val < inp[0])return -1;
      int hi=inp.length-1; int lo = 0;
      while(lo < hi && (hi-lo) > 1){
       int mid = lo + (hi-lo)/2;
       if (inp[mid] == val )
            return mid;            
       else if(inp[mid] < val ) 
            lo = mid;
       else
            hi = mid-1;
      }
      if(inp[hi]==val)return hi;
      return lo;
    }

Binary Search for find the closest bigger element

This is as same as the Binary Search for find the closest smaller element with the obvious change of

        
		else
            hi = mid;

in the if-else clause

    int findFirstBiggerBST(int[] inp,int val){
      if(val>inp[inp.length-1])return -1;
      int hi=inp.length-1; int lo = 0;
      while(lo < hi && (hi-lo) > 1){
       int mid = lo + (hi-lo)/2;
       if (inp[mid] == val )
            return mid;            
       else if(inp[mid] < val ) 
            lo = mid+1;
       else
            hi = mid;
      }
      if(inp[lo]>val)return lo;
      return hi;
    }

saved under Algorithm Tutorials/Binary Search by freebooksandarticles