Compare the runtime complexity of Linear Search and Binary Search

Problem

To implement linear search and binary search and compare their runtime complexity.

Task

(in Java)
search a integer in a array which input size varies 10 to 100,000, increasing each time 10 times. Array elements are all random number between 1 and 100,000. for each input size, using linear search and binary search to find the time that search uses(generate array and keyword not count in to search time).
T1 = System.nanoTime();
boolean = linearSearch(list, key);
T2 = System.nanoTime();
The time that search cost should be T1 – T2 ns or (T1 – T2) / 1000000 ms

Linear Search

This is the basic linear search pseudo code:

Procedure linear search(x: integer, a1, a2, ..., an: distinct integers)
i := 1
while(i ≤ n and x≠ai)
i := i + 1
if i ≤ n then location := i
else location := 0
return location(location is the subscript of the term that equals x, or is 0 if x is not found)

Or, we can understand that is search the keyword one by one through the array.

Binary Search

This is the basic binary search pseudo code:

procedure binary search(x: integer, a1, a2, ..., an: increasing integers)
i := 1 {i is left endpoint of search interval}
j "= n {j is right endpoint of search interval}
while i < j m := (floor)((i + j) / 2) if x > am then i := m + 1
else j := m
if x = ai then location := i
else location := 0
return location(location is the subscript i of the term ai equal to x, or - if x is not found)

The binary search can divided the array to two parts and compare with the middle one to decide which part should we choose and follow that step by several time, and we can just find the key word is the middle one or we cannot find it.

Code

// Chenran Jin
// Feb 6th 2017
import java.util.Arrays;

public class CJin {
    public static void main(String[] args) {
        for(int size = 10; size <= 100000; size *= 10){
            // Generate the list and keyword
            int[] list = new int[size];
            for(int index = 0; index < size; index++){
                list[index] = (int)(Math.random() * 100000 + 1);
            }
            Arrays.sort(list);
            int key = (int)(Math.random() * 100000 + 1);

            // call linearSearch(), get time and result
            long lt1 = System.nanoTime();
            boolean linearRes = linearSearch(list, key);
            long lt2 = System.nanoTime();
            long linearTime = lt2 - lt1;
            String linearResult = "";
            if(linearRes) {
                linearResult = "  item found  ";
            } else {
                linearResult = "item not found";
            }

            // call binarySearch(), get time and result
            long bt1 = System.nanoTime();
            boolean binaryRes = binarySearch(list, key);
            long bt2 = System.nanoTime();
            long binaryTime = bt2 - bt1;
            String binaryResult = "";
            if(binaryRes){
                binaryResult = "  item found  ";
            } else {
                binaryResult = "item not found";
            }

            // Show the result
            System.out.println("N = " + Integer.toString(size) + ": " + linearResult);
            System.out.println("Linear Search: " + linearTime);
            System.out.println("Binary Search: " + binaryTime);
            System.out.println();
        }
    }

    public static boolean linearSearch(int[] list, int key){
        boolean result = false;
        for (int index = 0; index < list.length; index++){
            if(list[index] == key){
                result = true;
            }
        }
        return result;
    }

    public static boolean binarySearch(int[] list, int key) {
        boolean result = false;
        int startPoint = 0;
        int endPoint = list.length - 1;
        while(endPoint >= startPoint){
            int middlePoint = (startPoint + endPoint) / 2;
            if(list[middlePoint] == key){
                result = true;
            }
            if(list[middlePoint] < key){
                startPoint = middlePoint + 1;
            }
            if(list[middlePoint] > key){
                endPoint = middlePoint -1;
            }
        }
        return result;
    }
}

Observations

And form the code, we can find the worst case in the linear search is O(N), and in the binary search is O(log2(N)). So, we can find that


We can easily find that ideal value’s rate is similar to the recorded time. Put everything We can learned that: if you need to search through a sorted array of integers and performance is important or you array cannot sort, then use linear search; but if your array has billions of elements, the binary search definitely can save your time.