Category: Search

public class ExponentialSearch {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int arr [] = {2,4,5,6,7,8,9,10,11,12,13,14,15};
		
		int elementToSearch = 12;
		
		System.out.println("Searching for the element ::"+elementToSearch);
		int result = exponentialSearch(arr, arr.length,elementToSearch);
		System.out.println("Element found at index ::"+result);
		
	}

	public static int exponentialSearch(int arr[],int len, int elementToSearch){
		
		if(arr[0]==elementToSearch)
			return 0;
		
		int i =2;
		while(i<len && arr[i]<elementToSearch){
			i=i*2;
		}
		
		System.out.println("i ::"+i);
		int endIndex = (i>len)?len:i;
		
		BinarySearch binary = new BinarySearch();
		return binary.binarySearch(arr, i/2,endIndex, elementToSearch);
	}
}

Output :

Searching for the element ::12
i ::16
Element found at index ::9

public class JumpSearch {

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		
		int arr[] = {0,1,21,32,44,56,61,76,83,94,101};
		
		int elementToSearch = 44;
		
		System.out.println("Searching for the element ::"+elementToSearch);
		
		int index = jumpSearch(arr,elementToSearch);
		
		
		System.out.println("Element found at index ::"+index);
	}

	public static int jumpSearch(int arr[], int elementToSearch){
		int index = -1;
		
		//finding the block size
		int blockSize = (int)Math.floor(Math.sqrt(arr.length));
		
		//finding the block where elementToSeach may be present;
		int blockStart = 0;
		while(arr[Math.min(blockSize, arr.length)-1] arr.length-1)
				return -1;
		}
		
		while(arr[blockStart] Math.min(blockSize, arr.length))
				return -1;
			
			if(arr[blockStart]==elementToSearch)
				return blockStart;
			
			
			blockStart++;
		}
		return index;
	}
	
}

Output :

Searching for the element ::44
Element found at index ::4

public class FibonacciSearch {

	public static void main(String[] args) {
		int arr[]={10,22,33,34,36,37,39,41,44,48,51,57};
		
		int n = arr.length;
		int x = 44;
		
		System.out.println("Element to Search ::"+x);
		
		int index = fibonacci(arr,x,n);
		
		System.out.println("Element found at location ::"+index);
	}

	public static int fibonacci(int arr[],int x, int n){
		
		//find smallest fibonacci number greater than or equal to n;
		int fibM2 = 0;
		int fibM1 = 1;
		int fibM = fibM1+fibM2;
		
		while(fibM1){
			int i = Math.min(offset+fibM2, n-1);
			
			if(arr[i]x){
				fibM = fibM2;
				fibM1 = fibM1 - fibM2;
				fibM2 = fibM - fibM1;
			}
			
			else 
				return i;
		}
		
		
		   if (fibM1 == 1 && arr[n-1] == x)
	            return n-1;
		   
		   
		return -1;
	}
}

Output

Element to Search ::44
Element found at location ::8

public class TernarySearch {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		int arr[] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18};
		
		int elementToSearch = 2;
		System.out.println("Searching for the element ::"+elementToSearch);
		
		int resultIndex = tarnarySearch(arr,elementToSearch,0,arr.length-1);
		
		System.out.println("element found at index ::"+resultIndex);

	}

	public static int tarnarySearch(int arr[],int elementToSearch,int startIndex, int endIndex){
		
		int mid1 = startIndex+(endIndex-startIndex)/3;
		
		int mid2 = startIndex + ((endIndex-startIndex)/3)+((endIndex-startIndex)/3);
		
		if(arr[startIndex]==elementToSearch)
			return startIndex;
		else if(arr[endIndex]==elementToSearch)
			return endIndex;
		else if(arr[mid1]==elementToSearch)
			return mid1;
		else if(arr[mid1]>elementToSearch)
			return tarnarySearch(arr,elementToSearch,startIndex,mid1-1);
		else if(arr[mid2]==elementToSearch)
			return mid2;
		else if(arr[mid2]>elementToSearch)
			return tarnarySearch(arr,elementToSearch,mid1,mid2-1);
		else if(arr[endIndex]>=elementToSearch)
			return tarnarySearch(arr,elementToSearch,mid2,endIndex);
			
		
		return -1;
	}
}

Output :

Searching for the element ::2
element found at index ::1

public class LinearSearch {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int arr[] = {1,2,3,4,5};
		int search_element=1;
		
		
		System.out.println("Element to be searched ::"+search_element);
		int index = search(arr,search_element);
		System.out.println("Element found at index ::"+index);
	}

	
	public static int search(int arr[],int search_element){
		int index=-1;
		int len = arr.length;
		int left = 0;
		int right = len-1;
		
		for(;left<=right;){
			
			if(arr[left]==search_element)
				return left;
			if(arr[right]==search_element)
				return right;
			
			left++;
			right--;
			
		}
		
		
		
		return index;
	}
}

Output :

Element to be searched ::1
Element found at index ::0

public class BinarySearch {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		int arr[] ={2,3,4,10,40};
		int element_To_Search = 400;
		int len = arr.length;
		
		
		System.out.println("Searching for the element :: "+element_To_Search);
		int indexFound = binarySearch(arr,0,len-1,element_To_Search);

		if(indexFound==-1)
			System.out.println("Element not found::");
		else
			System.out.println("Element found at index ::"+indexFound);
	}

	public static int binarySearch(int [] arr, int startIndex, int endIndex, int elementToSearch){
		if(endIndex>=startIndex){
			int mid = (endIndex+startIndex)/2;
			
			if(arr[mid]==elementToSearch)
				return mid;
			
			if(arr[mid]>elementToSearch)
				return binarySearch(arr,startIndex,mid,elementToSearch);
			else
				return binarySearch(arr,mid+1,endIndex,elementToSearch);
			
		}
		
		return -1;
	}
}

Searching for the element :: 40
Element found at index ::4