×

Welcome to TagMyCode

Please login or create account to add a snippet.
 

BinarySearch.java

0
0
 
0
Language: Java
Posted by: Shamir Yona
Added: Sep 18, 2015 3:46 PM
Modified: Sep 18, 2015 3:47 PM
Views: 13
Tags: java binarysearch
A class, which includes a basic Binary Search and a search, for a duplicate value, which is based on Binary Search
  1. /*
  2.  * To change this license header, choose License Headers in Project Properties.
  3.  * To change this template file, choose Tools | Templates
  4.  * and open the template in the editor.
  5.  */
  6. package OtherTests;
  7.  
  8. /**
  9.  *
  10.  * @author shayzukerman
  11.  */
  12. public class BinarySearch
  13. {
  14.     int[] arr;
  15.    
  16.     public BinarySearch(int[] arr)
  17.     {
  18.         this.arr = arr;
  19.     }
  20.    
  21.     int[] fillArray(int start, int end, int skipOff, int dupOff)
  22.     {
  23.         int arrSize = end - start + 1;
  24.  
  25.         if (skipOff == dupOff && skipOff >= start && skipOff <= end)
  26.             throw new IllegalArgumentException("SkipOff == dupOff");
  27.        
  28.         if (skipOff >= start && skipOff <= end)
  29.             arrSize--;
  30.         if (dupOff >= start && dupOff <= end)
  31.             arrSize++;
  32.         int[] retArr = new int[arrSize];
  33.        
  34.         int off = 0;
  35.         for (int val = start; val <= end; val++)
  36.         {
  37.             if (val != skipOff)
  38.                 retArr[off++] = val;
  39.             if (val == dupOff)
  40.                 retArr[off++] = val;
  41.         }
  42.         return(retArr);
  43.     }
  44.  
  45.     public void setArr(int[] arr)
  46.     {
  47.         this.arr = arr;
  48.     }
  49.    
  50.     public String arr2Str()
  51.     {
  52.         StringBuilder buf = new StringBuilder();
  53.         for (int i = 0; i < arr.length; i++)
  54.             buf.append(String.format("%d%s", arr[i], ((i < arr.length - 1) ? ", " : "")));
  55.         return("{" + buf.toString() + "}");
  56.     }
  57.    
  58.     public boolean doSearch(int val, int from, int to)
  59.     {
  60.         boolean retVal = false;
  61.        
  62.         int low = from;
  63.         int high = to;
  64.         int mid;
  65.         int midVal;
  66.        
  67.         while (high >= low)
  68.         {
  69.             mid = (low + high) / 2;
  70.             midVal = arr[mid];
  71.            
  72.             if (midVal == val)
  73.             {
  74.                 retVal = true;
  75.                 break;
  76.             }
  77.             else if (midVal < val)
  78.                 low = mid + 1;
  79.             else
  80.                 high = mid - 1;
  81.         }
  82.        
  83.         return(retVal);
  84.     }
  85.    
  86.     public int findDupVal()
  87.     {
  88.         int retVal = -1;
  89.        
  90.         int low = 0;
  91.         int high = arr.length - 1;
  92.         int mid;
  93.         int midVal;
  94.        
  95.         while (high >= low)
  96.         {
  97.             mid = (low + high) / 2;
  98.             midVal = arr[mid];
  99.                        
  100.             if (mid > midVal)
  101.             {
  102.                 // curr pos is before the duplicate location
  103.                 if (mid > 0 && arr[mid - 1] == mid - 1)
  104.                 {
  105.                     retVal = midVal;
  106.                     break;
  107.                 }
  108.                 high = mid - 1;
  109.             }
  110.             else if (mid <= midVal)
  111.             {
  112.                 low = mid + 1;
  113.             }
  114.         }
  115.        
  116.         return(retVal);
  117.     }
  118.    
  119.    
  120.     public static void main(String[] args)
  121.     {
  122.         int[] arr = {1, 2, 3, 7, 9};
  123.        
  124.         BinarySearch binSearch = new BinarySearch(arr);
  125. //        boolean found = binSearch.doSearch(2, 0, arr.length - 1);
  126. //        System.out.println("found: " + found);
  127.        
  128.           binSearch.setArr(binSearch.fillArray(0, 99, -1, 57));
  129. //        System.out.println(binSearch.arr2Str());
  130.        
  131.         //binSearch.setArr(binSearch.fillArray(0, 3, -1, 1));
  132.         System.out.println(binSearch.arr2Str());
  133.         int dupVal = binSearch.findDupVal();
  134.         System.out.println("dupVal: " + dupVal);
  135.     }
  136. }
  137.  

Write a comment

To post comments, please log in or register.