/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
package OtherTests;
/**
*
* @author shayzukerman
*/
public class BinarySearch
{
int[] arr;
public BinarySearch(int[] arr)
{
this.arr = arr;
}
int[] fillArray(int start, int end, int skipOff, int dupOff)
{
int arrSize = end - start + 1;
if (skipOff == dupOff && skipOff >= start && skipOff <= end)
if (skipOff >= start && skipOff <= end)
arrSize--;
if (dupOff >= start && dupOff <= end)
arrSize++;
int[] retArr = new int[arrSize];
int off = 0;
for (int val = start; val <= end; val++)
{
if (val != skipOff)
retArr[off++] = val;
if (val == dupOff)
retArr[off++] = val;
}
return(retArr);
}
public void setArr(int[] arr)
{
this.arr = arr;
}
{
StringBuilder buf = new StringBuilder();
for (int i = 0; i < arr.length; i++)
buf.
append(String.
format("%d%s", arr
[i
],
((i
< arr.
length - 1) ? ", " : ""))); return("{" + buf.toString() + "}");
}
public boolean doSearch(int val, int from, int to)
{
boolean retVal = false;
int low = from;
int high = to;
int mid;
int midVal;
while (high >= low)
{
mid = (low + high) / 2;
midVal = arr[mid];
if (midVal == val)
{
retVal = true;
break;
}
else if (midVal < val)
low = mid + 1;
else
high = mid - 1;
}
return(retVal);
}
public int findDupVal()
{
int retVal = -1;
int low = 0;
int high = arr.length - 1;
int mid;
int midVal;
while (high >= low)
{
mid = (low + high) / 2;
midVal = arr[mid];
if (mid > midVal)
{
// curr pos is before the duplicate location
if (mid > 0 && arr[mid - 1] == mid - 1)
{
retVal = midVal;
break;
}
high = mid - 1;
}
else if (mid <= midVal)
{
low = mid + 1;
}
}
return(retVal);
}
public static void main
(String[] args
) {
int[] arr = {1, 2, 3, 7, 9};
BinarySearch binSearch = new BinarySearch(arr);
// boolean found = binSearch.doSearch(2, 0, arr.length - 1);
// System.out.println("found: " + found);
binSearch.setArr(binSearch.fillArray(0, 99, -1, 57));
// System.out.println(binSearch.arr2Str());
//binSearch.setArr(binSearch.fillArray(0, 3, -1, 1));
System.
out.
println(binSearch.
arr2Str()); int dupVal = binSearch.findDupVal();
System.
out.
println("dupVal: " + dupVal
); }
}
Loading...