Created: 2023-09-02 19:12
Status: #concept
Subject: Programming
Tags: Algorithm

Binary Search

It is an information traversal algorithm in order to find an element in a SORTED list.

  • It's Time Complexity is O(log n) because we half our search area every iteration.

The Algorithm

  1. Data is searched in an ordered array or list.
  2. Search begins in the middle arr.length / 2, rounded down.
  3. The the value of the examined middle point is not the value that is searched for, we exclude half of the previous search are and move to examine the middle point of the remaining area.
  4. If the examined middle value is the value that is searched for, we return the index of that middle point.
  5. If the search area does not exist anymore (every index has been excluded from the list of possinilities), the value of -1 is returned. It indicates that the value in question cannot be found.

Pseudocode

// assuming the variable searched exits
// assuming the variable list exits
begin = 0 // the 0th index of the list (i.e, the first index of the list)
end = size(list) - 1 // the last index in the list

repeat until begin is larger than end:
    middle = (end + begin) / 2

    if the value at list[middle] is searched
        return the value of the variable middle

    if the value at list[middle] is smaller than searched
        begin = middle + 1

    if the value at list[middle] is larger than searched
        end = middle - 1

return value -1

Java

public static int binarySearch(ArrayList<Integer> arr, int toSearch) {
    int start = 0, end = arr.size() - 1;
    
    while (start < end) {
        int middle = (start + end) / 2;
        long middleValue = books.get(middle);
        
        if (middleValue == toSearch) {
            return middle;
        } else if (middleValue < toSearch) {
            start = middle + 1;
        } else if (middleValue > toSearch) {
            end = middle - 1;
        }
    }
    
    return -1;
}

References