Linear Search vs Binary Search Example (Based on time processing)

custombinarysearch.java

import java.util.Arrays;

public class BinarySearch {

	/**
	 * Implementation of a Binary Search Returns -1 if no match found
	 * 
	 * @param sortedArray
	 * @param target
	 * @return
	 */
	static int binarySearch(int[] sortedArray, int target) {

		int low = 0;
		int high = sortedArray.length - 1;

		// Loop on O(log n) time
		while (low <= high) {

			// Set the middle value
			int mid = (low + high) / 2;
			int midVal = sortedArray[mid];

			if (midVal < target) {
				low = mid + 1;
			} else if (midVal > target) {
				high = mid - 1;
			} else {
				return mid;
			}

		}
		return -1;
	}

	/**
	 * Linear Search
	 * 
	 * @param array
	 * @param target
	 * @return
	 */
	static int linearSearch(int[] array, int target) {

		for (int i = 0; i < array.length; i++) {
			if (array[i] == target) {
				return i;
			}
		}

		return -1;
	}

	/**
	 * implement a binary search
	 * 
	 * @param args
	 */
	public static void main(String[] args) {

		int[] sortArr = new int[599999999];
		for (int i = 1; i < 599999999; i++) {
			sortArr[i] = i;
		}

		int[] smallSortArr = { 1, 2, 2, 2, 3, 4, 5, 5, 6, 7, 8, 9, 9, 10, 11, 12, 12, 13, 14, 15, 16, 16, 16, 18, 19, 20 };

		long startTimer = 0;
		int sTarget = 9;
		int bTarget = 199699890;
		
		// Show Data set
		startTimer = System.currentTimeMillis();
		System.out.println("1st Sorted Array Set: " + Arrays.toString(smallSortArr));
		System.out.println("Number to search: " + sTarget + "\n");
		System.out.println("2nd Sorted Array Set: " + " [1 to " + sortArr.length + "]" );
		System.out.println("Number to search: " + bTarget + "\n\n");
		
		// Call the linearSearch function
		startTimer = System.currentTimeMillis();
		System.out.println("Linear Search");
		System.out.println("\t"+ sTarget + " is at index:\t" + linearSearch( smallSortArr, sTarget));
		System.out.println("\t"+bTarget + " is at index:\t" + linearSearch(sortArr, bTarget));
		System.out.println("\tProcessing Time:\t" + (System.currentTimeMillis() - startTimer) + " ms \n\n");

		// Call the Custom Binary Search function
		startTimer = System.currentTimeMillis();
		System.out.println("Binary Search");
		System.out.println("\t"+ sTarget + " is at index:\t" + binarySearch( smallSortArr, sTarget));
		System.out.println("\t"+bTarget + " is at index:\t" + binarySearch(sortArr, bTarget));
		System.out.println("\tProcessing Time:\t" + (System.currentTimeMillis() - startTimer) + " ms \n\n");

		// Call Java's built-in Binary Search function
		startTimer = System.currentTimeMillis();
		System.out.println("Built-In Java Binary Search");
		System.out.println("\t"+ sTarget + " is at index:\t" + Arrays.binarySearch( smallSortArr, sTarget));
		System.out.println("\t"+bTarget + " is at index:\t" + Arrays.binarySearch(sortArr, bTarget));
		System.out.println("\tProcessing Time:\t" + (System.currentTimeMillis() - startTimer) + " ms \n\n");

		
	}

}