Binary Search

This is very important to learn.

Binary searching is a very very effective search metod.

A binary search locates a value by determining if the first or second half, the repeting the search in one of the halves, therefor binary search is an O(log(N)) algoritm.




---------------------------------------------------
public class Main
{

private static LinkedList lista = new LinkedList();
private static int[] a = new int[10000000+1];


public static void main(String[] args)
{


for (int i = 0; i <= 10000000; i++)
a = i;

System.out.println("Start....");

search(10000000);
System.out.println("Done");

}




public static int search(int v)
{

int low = 0;
int high = a.length - 1;

while(low <= high)
{

int mid = (low + high) / 2;
int diff = a[mid] - v;

if(diff == 0)
return mid;

else if(diff < 0)
low = mid + 1;


else
high = mid - 1;
}


return -1;
}


}
---------------------------------------------------
public class LinkedList
{
private IntNode head;

public LinkedList()
{
head = null;
}

public void add (int data)
{
IntNode nyNode = new IntNode(null, data);
IntNode current;


if (head == null)
head = nyNode;

else
{
current = head;
while (current.getNext() != null)
current = current.getNext();

current.setNext(nyNode);
}
}


}

---------------------------------------------------
public class IntNode
{
private IntNode next;
private int data;

public IntNode(IntNode next, int data)
{
this.next = next;
this.data = data;

}

public IntNode getNext()
{
return next;
}

public void setNext(IntNode inNode)
{
next = inNode;
}

public int getData()
{
return data;
}


}