Binary Search

algorithm.md

###Binary search - Applicable to sorted Iterables

Binary search exploits the relational difference between the elements and hence can be implemented upon almost any types of iterable, whether it be array, list, linked-list, etc stored it sorted order.

BINARY_SEARCH(ITERABLE L, start, final, element_to_search):
	IF start <= final:
		middle = FLOOR[(start + final) / 2]
		IF element_to_search < L[middle]:
			RETURN BINARY_SEARCH(L, start, mid - 1, element_to_search)
		ELSE IF element_to_search > L[middle]:
			RETURN BINARY_SEARCH(L, mid + 1, final, element_to_search)
		ELSE
			RETURN middle
		END IF
	END IF
	RETURN FALSE
END BINARY_SEARCH

Initially invoke with start as 0 and final as n where n is the last index of iterable.
It compares the element at the middle of concerned domain with the element_to_search.
Since the elements are in sorted order, it adjusts the range - the domain to look for accordingly.
Some fundas -

• Suppose the iterable is sorted in increasing order and if the element_to_search is greater than the element at middle index, then it is for sure that if it exists, it will exist after this element.
• Therefore, our concerned domain (the range in which we will be searching for our element) has been reduced to [middle + 1, final] from [start, final], half to be more precise.
• Similarly, if the element_to_search is lesser than the element at middle, our reduced domain would have been [start, middle - 1]

After every step the domain is reduced to half of what it used to be. And theryby it would be taking a maximum of log n steps before it could conclude a result.
The best case would be when the element_to_search is present at FLOOR[L.length / 2]. Hence it will be fetched in a single step i.e. O(1).
The average as well as the worst case will be taking up O(log n).

**Note: log base 2. Also assumed iterable was pre-sorted. If not, an additional complexity for sorting must be added alongwith.

binary-search.c

/*
	BINARY SEARCH
	0 based indexing
	array as iterable
	presorted in increasing order
	recursive method
	** for TURBO C, remove // from commented statements
*/

#include<stdio.h>
//#include<conio.h>

/* Since there's no boolean type in c, and -1 will never appear as an index */
#define FALSE -1

int BINARY_SEARCH(int *arr, int start, int final, int element_to_search){
	int middle;
	
	if(start <= final){
		middle = (start + final) / 2;
		if(element_to_search < arr[middle])
			return BINARY_SEARCH(arr, start, middle - 1, element_to_search);
		else if(element_to_search > arr[middle])
			return BINARY_SEARCH(arr, middle + 1, final, element_to_search);
		else
			return middle;
	}
	return FALSE;
}

int main(){
	int index, element_to_search, arr_length = 10;
	int arr[] = { -11, 6, 7 , 9, 29, 70, 76, 132, 332, 790 };

	//clrscr();

	printf("\nEnter element to search: "); scanf("%d", &element_to_search);
	
	index = BINARY_SEARCH(arr, 0, arr_length - 1, element_to_search);

	if(index != FALSE){
		printf("The search for %d succeeded. Found at index %d i.e. position %d.", element_to_search, index, index + 1);
	}else{
		printf("The search for %d failed. NOT FOUND.", element_to_search);
	}

	printf("\n");
	//getch();
	return 0;
}

BinarySearch.java

/*
	BINARY SEARCH
	0 based indexing
	array as iterable
	presorted in increasing order
	recursive method
	Save File as BinarySearch.java
*/

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class BinarySearch{

	static int BINARY_SEARCH(int[] arr, int start_index, int final_index, int element_to_search){
		/* Why static? Since we are calling from main, which itself is static */
		
		if(start_index <= final_index){
			int middle_index = (start_index + final_index) / 2;
			if(element_to_search < arr[middle_index])
				return BINARY_SEARCH(arr, start_index, middle_index - 1, element_to_search);
			else if(element_to_search > arr[middle_index])
				return BINARY_SEARCH(arr, middle_index + 1, final_index, element_to_search);
			else
				return middle_index;
		}
		return -1;
	}	
 
	public static void main(String s[]) throws NumberFormatException, IOException{
		BufferedReader ip = new BufferedReader(new InputStreamReader(System.in));
		int index, element_to_search;
		int arr[] = { -11, 6, 7 , 9, 29, 70, 76, 132, 332, 790 };

		System.out.print("\nEnter element to search: "); element_to_search = Integer.parseInt(ip.readLine());
		
		index = BINARY_SEARCH(arr, 0, arr.length - 1, element_to_search);

		if(index != -1){
			System.out.print("The search for " + element_to_search + " succeeded. Found at index " + index + " i.e. position " + (index + 1) + ".");
		}else{
			System.out.print("The search for " + element_to_search + " failed. NOT FOUND.");
		}

		System.out.print("\n");
	}
}