BINARY SEARCH IN JAVA

BINARY SEARCH:

• Binary Search is one of the fastest searching algorithms.
• It is used for finding the location of an element in a linear array.
• It works on the principle of divide and conquer [கைப்பற்றும்] technique.
• Binary Search Algorithm can be applied only on Sorted arrays.
• To apply binary search on an unsorted array,
  • First, sort the array using some sorting technique.
  • Then, use binary search algorithm.

A simple Binary Search Algorithm:

• Calculate the mid element of the collection.
• Compare the key items with the mid element.
• If key = middle element, then we return the mid index position.
• Else If key > mid element, then the key lies in the right half of the collection. Thus repeat steps 1 to 3 on the right half of the collection.
• Else key < mid element, then the key lies in the left half of the collection. Thus repeat steps 1 to 3 on the left half of the collection.

For example, take the following sorted array:

---

TIME COMPLEXITY:

• Binary Search divides the array into half each time.
• So, its time complexity is O(log(N))

SPACE COMPLEXITY:

• Binary search takes constant O(1) space.
• Space taken by this algorithm is same for any number of elements in the array.

---

Ex 1: Sorted array

import java.util.Scanner;

public class Practice {
	
	Scanner sc = new Scanner(System.in);
	
	static 
	{
		System.out.println("Enter array length");
	}

	int len = sc.nextInt();
	int array[] = new int[len];

	public static void main(String[] args) 
	{
		Practice obj = new Practice();
		obj.method1();
		obj.searchMethod();
	}

	public void method1() 
	{
		System.out.println("Enter array value");
		for (int i = 0; i < array.length; i++) 
		{
			array[i] = sc.nextInt();
		}

		System.out.println("Show array value");
		for (int i = 0; i < array.length; i++) 
		{
			System.out.print(array[i] + " ");
		}
		System.out.println();
	}
	
	public void searchMethod()
	{
		System.out.println("Enter the search number");
		int search = sc.nextInt();

		int start = 0;
		int end = array.length - 1;

		while (start <= end) {
			int middle = (start + end) / 2;

			if (search == array[middle]) 
			{
				System.out.println("Search number is placed at " + middle + " position");
				break;
			} 
			else if (search > array[middle]) 
			{
				start = middle + 1;
			} 
			else if (search < array[middle]) 
			{
				end = middle - 1;
			}
		}

		if (start > end) 
		{
			System.out.println("Search number is not found");
		}
		searchAgain();
	}
	
		public void searchAgain()
		{
		System.out.println("Press 1 for search another number");
		System.out.println("Press 2 for exit");
		int press = sc.nextInt();
		
		switch(press)
		{
		case 1 :
			searchMethod();
			break;
		case 2 :
			break;
		default:
			System.out.println("Kindly press correct number");
			searchAgain();
			break;
		}
	}
}

Output:

Enter array length
5
Enter array value
12
23
34
45
56
Show array value
12 23 34 45 56
Enter the search number
76
Search number is not found
Press 1 for search another number
Press 2 for exit
23
Kindly press correct number
Press 1 for search another number
Press 2 for exit
90
Kindly press correct number
Press 1 for search another number
Press 2 for exit
9
Kindly press correct number
Press 1 for search another number
Press 2 for exit
25
Kindly press correct number
Press 1 for search another number
Press 2 for exit
1
Enter the search number
12
Search number is placed at 0 position
Press 1 for search another number
Press 2 for exit
2

---

Ex 2: Unsorted array

• If given array is not ascending or descending order, sorting the array first.
• Then search the number in array.

import java.util.Scanner;

public class Practice {
	
	Scanner sc = new Scanner(System.in);
	
	static 
	{
		System.out.println("Enter array length");
	}

	int len = sc.nextInt();
	int array[] = new int[len];

	public static void main(String[] args) 
	{
		Practice obj = new Practice();
		obj.method1();
		obj.sortMethod();
		obj.searchMethod();
	}

	public void method1() 
	{
		System.out.println("Enter array value");
		for (int i = 0; i < array.length; i++) 
		{
			array[i] = sc.nextInt();
		}

		System.out.println("Show array value");
		for (int i = 0; i < array.length; i++) 
		{
			System.out.print(array[i] + " ");
		}
		System.out.println();
	}
	
	public void sortMethod()
	{
		for(int round=1;round<array.length;round++)
		{
		for(int i=0; i<array.length-round;i++)
		{
			if(array[i]>array[i+1])
			{
			int temp = array[i];
			array[i] = array[i+1];
			array[i+1] = temp;
			}
		}
		}
		System.out.println("After Sorting");
		for(int i = 0; i<array.length; i++)
		{
			System.out.print(array[i] + " ");
		}
        System.out.println();
	}
	
	public void searchMethod()
	{
		System.out.println("Enter the search number");
		int search = sc.nextInt();

		int start = 0;
		int end = array.length - 1;

		while (start <= end) {
			int middle = (start + end) / 2;

			if (search == array[middle]) 
			{
				System.out.println("Search number is placed at " + middle + " position");
				break;
			} 
			else if (search > array[middle]) 
			{
				start = middle + 1;
			} 
			else if (search < array[middle]) 
			{
				end = middle - 1;
			}
		}

		if (start > end) 
		{
			System.out.println("Search number is not found");
		}
		searchAgain();
	}
	
		public void searchAgain()
		{
		System.out.println("Press 1 for search another number");
		System.out.println("Press 2 for exit");
		int press = sc.nextInt();
		
		switch(press)
		{
		case 1 :
			searchMethod();
			break;
		case 2 :
			break;
		default:
			System.out.println("Kindly press correct number");
			searchAgain();
			break;
		}
	}
}

Output:

Enter array length
7
Enter array value
100
17
200
29
90
99
300
Show array value
100 17 200 29 90 99 300
After Sorting
17 29 90 99 100 200 300
Enter the search number
100
Search number is placed at 4 position
Press 1 for search another number
Press 2 for exit
20
Kindly press correct number
Press 1 for search another number
Press 2 for exit
1
Enter the search number
20
Search number is not found
Press 1 for search another number
Press 2 for exit
2

---