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

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