# Binary Search

guess a number between 1-100

only works with sorted lists

split in half everytime until you get to the number

for any list n it will take log2 n steps in worst case

## Java

``````public class BinarySearch {

// has to return boxed integer in order to comfort to interface defined in the book
private static Integer binarySearch(int[] list, int item) {
int low = 0;
int high = list.length - 1;

while (low <= high) {
int mid = (low + high) / 2;
int guess = list[mid];
if (guess == item) {
return mid;
}
if (guess > item) {
high = mid - 1;
} else {
low = mid + 1;
}
}

return null;
}

public static void main(String[] args) {
int[] myList = {1, 3, 5, 7, 9};

System.out.println(binarySearch(myList, 3)); // 1
System.out.println(binarySearch(myList, -1)); // null
}
}``````

## Python

``````def binary_search(list, item):
# low and high keep track of which part of the list you'll search in.
low = 0
high = len(list) - 1

# While you haven't narrowed it down to one element ...
while low <= high:
# ... check the middle element
mid = (low + high) // 2
guess = list[mid]
# Found the item.
if guess == item:
return mid
# The guess was too high.
if guess > item:
high = mid - 1
# The guess was too low.
else:
low = mid + 1

# Item doesn't exist
return None

my_list = [1, 3, 5, 7, 9]
print binary_search(my_list, 3) # => 1

# 'None' means nil in Python. We use to indicate that the item wasn't found.
print binary_search(my_list, -1) # => None``````