Binary search

1.Binary search

• Choose an element in at the mid-point at a sorted list

• Check whether it's smaller than or greater than the element you are looking for

2.Code

• Iterative (take O (log n) time )

public static int binarySearch(int[] sortedList, int number) {
    int min = 0;
    int max = sortedList.length - 1;
    
    while (min <= max) {
        int mid = min + (max - min) / 2;
        if (sortedList[mid] == number) {
            return mid;
        }
        if (sortedList[mid] > number) {
            max = mid - 1;
        } else {
            min = mid + 1;
        }
    }
    return -1;
}

• recursive (take O (log n) time, take recursive stack)

public static int binarySearch(int[] sortedList, int number, int max, int min) {
    if (min > max) {
        return -1;
    }
    int mid = min + (max - min) / 2;
    if (sortedList[mid] == number) {
        return mid;
    }
    if (sortedList[mid] > number) {
        reurn binarySearch(sortedList, number, max, mid - 1);
    } else {
        reurn binarySearch(sortedList, number, mid + 1, max);
    }
}

3.Complexity

• The complexity is O(LogN)