2022년 2월 21일 월요일

what is Binary Search Algorithm

2월 21, 2022 Eunhan's library

Binary Search Algorithm

Definition

check middle of list first. if the number is smaller than what you are looking for, check right side only and doing this continuously. It will decrease search list in half.

pre-condition : the list sorted
pre-condition : when new data inserted, need to sort
Since it need to sort when new data inserted, it can be very slow if there are a lot of insertion
divide-and-conquer technique

Time complexity

$O(log\; n)$

Example

import java.util.NoSuchElementException;

public class Main {

    public static void main(String[] args) {

        int[] inputList = {1, 9, 44, 55, 88};
        int value = 55;

        System.out.println(getIndexValueArr(inputList, value));

    }

    private static int getIndexValueArr(int[] input, int value) {
        return binarySearchRecur(input, 0, input.length - 1, value);

    }

    private static int binarySearchRecur(int[] input,
                                         int mostLeft,
                                         int mostRight,
                                         int value) {
        if (mostRight < mostLeft) { /*value not found*/
            throw new NoSuchElementException();
        }

        int mid = mostLeft + ((mostRight - mostLeft) / 2);

        if (input[mid] == value) { /*found the value*/
            return mid;
        } else if (input[mid] > value) { /*value is left side*/
            return binarySearchRecur(input, mostLeft, mid - 1, value);
        } else { /*value is right side*/
            return binarySearchRecur(input, mid + 1, mostRight, value);
        }
    }
}