# 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)&#x20;
