Binary Search

Introduction

This is one of the simplest search techniques that involves a intuitive way of searching for an item in a sorted list. Yes the it requires to be sorted in some order that supports searching.

For an example you may look for a certain page in a book. First you get the page number from the index at the end of the book. Then you randomly open the book and see it's page number. Say you have opened page 250, out of 500 pages and what you really need is page 256. Now it's obvious that the required page is at the latter half of the book.

Lets make this more general to make an algorithm out of it.

Divide the data set into two components.
Compare the last component of the first set, if the required item is greater in value, search in the latter half.
Else search in the first half.

Pseudo code

function BinarySearch(array, key, start, end)

        if(start > end)

                return -1 // Item not found

        mid = ( start + end) / 2

        if(array[mid] == key)

                return mid

        else if(array[mid] > key)

                return BinarySearch(array, key, mid + 1, end)

        else

                return BinarySearch(array, key, start, mid - 1)

Java Code

	package SearchingAndSorting;
	/**
	* Created by Anuradha on 3/6/2016.
	*/
	public class BinarySearch {
	private int[] array;
	public BinarySearch(int[] arr) {
	this.array = arr;
	}
	// Method to be called by the user
	public int binarySearch(int key) {
	return binarySearch(key, 0, array.length - 1);
	}
	// Method that will split and search in sub array determined by indices start and end
	private int binarySearch(int key, int start, int end) {
	// If the key is not available
	if (end < start) {
	return -1;
	}
	// If the key is present
	else {
	// Make a mid point pivot
	int mid = (start + end) / 2;
	// If the key is found
	if (array[mid] == key) {
	return mid;
	}
	// If key is in the array above the mid point
	else if (array[mid] < key) {
	return binarySearch(key, mid + 1, end);
	}
	// If the key resides in the first half
	else {
	return binarySearch(key, start, mid - 1);
	}
	}
	}
	public int ordinarySearch(int key) {
	for (int i = 0; i < array.length; i++) {
	if (key == array[i]) {
	return i;
	}
	}
	return -1;
	}
	public static void main(String[] args) {
	// Generating a sorted array
	int[] arr = new int[100000000];
	for (int i = 0; i < 100000000; i++) {
	arr[i] = i + 1;
	}
	BinarySearch bs = new BinarySearch(arr);
	long time = System.currentTimeMillis();
	System.out.println(bs.binarySearch(100000000));
	System.out.println("Time for binary Search = " + (System.currentTimeMillis() - time));
	// 1 Milli second
	time = System.currentTimeMillis();
	System.out.println(bs.ordinarySearch(100000000));
	// 87 milli seconds
	System.out.println("Time for ordinary Search = " + (System.currentTimeMillis() - time));
	}
	}

view raw binarySearch.java hosted with ❤ by GitHub

Feel free to visit the original repository of algorithms at:
URL https://github.com/anuradhawick/Algorithms