Giudoku Official Site
Binary search

The binary search is a more difficult but more efficient searching algorithm. In fact, its complexity does not change if the element is in different positions, like with the linear search.
But the binary search must operate on a sorted array! In fact, the "modus operandi" is

Array: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. Number: 9

1. Compare 9 with the middle element, that is, 5. If they match, we're done.
2. Look for 9 in just one subarray, the right one if 9 is bigger than 5, the left one otherwise.
3. Repeat the steps

The cycle (or recursion) stops when we find the element, or when we receive a 0-sized array as input (element not found).
The running time can be expressed via recurrence: T(n) = T(n/2) + Theta(1)
This falls in the 2nd case of the Master Theorem, so the result is T(n) = Theta(logn).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
import java.util.Arrays;

public class BinarySearch
{
	public static void main(String[] args)
	{
		int[] v1 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20};
		int[] elements = {6, 16, 22};
		
		System.out.println("Array is: " + Arrays.toString(v1));

		for (int i = 0; i < elements.length; i++)
		{
			System.out.println("Searching element " + elements[i] + " returned " + binarySearch(v1, elements[i], 0, v1.length - 1));
		}
	}
	
	public static boolean binarySearch(int[] V, int element, int low, int high)
	{
		int middle;
		
		while (low <= high)
		{
			middle = (low + high) / 2;
			
			if (element == V[middle])
			{
				return true;
			}
			else if (element < V[middle])
			{
				high = middle - 1;
			}
			else
			{
				low = middle + 1;
			}
		}
		
		return false;
	}

}
				


And now a recursive version! The base case is easy: given low as the lowest index and high as the highest index in the array, if low > high we didn't find the element.
Otherwise, we check the middle element, and if it doesn't correspond, call again the method on the correct subarray, modifying low and high.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
import java.util.Arrays;

public class RecursiveBinarySearch
{
	public static void main(String[] args)
	{
		int[] v1 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20};
		int[] elements = {6, 16, 22};
		
		System.out.println("Array is: " + Arrays.toString(v1));

		for (int i = 0; i < elements.length; i++)
		{
			System.out.println("Searching element " + elements[i] + " returned " + recursiveBinarySearch(v1, elements[i], 0, v1.length - 1));
		}
	}
	
	public static boolean recursiveBinarySearch(int[] V, int element, int low, int high)
	{
		int middle;
		
		if (low > high)
		{
			return false;
		}
		
		middle = (low + high) / 2;
		if (V[middle] == element)
		{
			return true;
		}
		else if (element < V[middle])
		{
			return recursiveBinarySearch(V, element, low, middle - 1);
		}
		
		return recursiveBinarySearch(V, element, middle + 1, high);
	}

}