Binary Search

Binary Search

Imagine you need to find the meaning of the word "Zoology" in an English dictionary. Would you start from the first page and flip through every single page until you reach Z? Of course not. You know the dictionary is arranged alphabetically, so you go straight to the second half — the section containing words that start with Z. Similarly, if you wanted "Biology," you would open the first half. This is the core idea behind binary search: using the fact that the data is already ordered to skip large portions of the list and find what you need much faster.

Binary search is a search technique that exploits the ordering of elements in a list. For numbers, the list must be sorted in either ascending or descending order. For text, it must be arranged alphabetically (a to z or z to a). If the list is not sorted, binary search cannot be used — you would have to fall back on linear search.

How Binary Search Works

The algorithm compares the key (the value you are searching for) with the element at the middle of the sorted list. This comparison has three possible outcomes:

1. The middle element matches the key — search is successful and ends immediately.
2. The middle element is greater than the key — the key, if present, must lie in the first half of the list. The second half is discarded.
3. The middle element is less than the key — the key, if present, must lie in the second half. The first half is discarded.

After each unsuccessful comparison, the search area is reduced by half. The process repeats on the remaining portion of the list until either the key is found or the remaining list contains only one element. If that single element is not the key, the search is unsuccessful — the key is not in the list.

Handling Even Number of Elements

When the list has an even number of elements, the middle position is calculated using floor division (//). For example, if there are 10 elements, mid = 10 // 2 = 5. Since list indexing starts at 0, the element at index 5 is actually the sixth element. In this case, the first half would contain 5 elements (indices 0 to 4) and the second half would contain 4 elements (indices 6 to 9).

Why It Is Called Binary Search

Each unsuccessful comparison still gives useful information — it tells you whether the key lies before or after the current middle position. This information allows you to narrow down the search area. Because every unsuccessful comparison reduces the number of remaining elements by half, the technique is called binary search.

Algorithm 6.2: Binary Search

Given a sorted list numList of n elements and a key value K, the binary search algorithm proceeds as follows:

Step 1: Set first = 0, last = n-1

Step 2: Calculate mid = (first + last) // 2

Step 3: While first <= last, repeat Step 4

Step 4:

• If numList[mid] == K, print "Element found at position mid+1" and stop
• Else if numList[mid] > K, set last = mid - 1
• Else set first = mid + 1 Step 5: Print "Search unsuccessful"

Worked Example

Consider the sorted list:

numList = [2, 3, 5, 7, 10, 11, 12, 17, 19, 23, 29, 31, 37, 41, 43]

Searching for key = 17

The key is found in just 1 iteration because it is the middle element. This is the minimum work binary search can do.

Searching for key = 2

The algorithm required 4 iterations to narrow down to a single element. This is the maximum work needed to find a key in this list.

Notice how the number of elements halves each time: 15 → 7 → 3 → 1.

Python Implementation

Program 6-2: Binary Search

def binarySearch(list, key):
    first = 0
    last = len(list) - 1
    while(first <= last):
        mid = (first + last)//2
        if list[mid] == key:
            return mid
        elif key > list[mid]:
            first = mid + 1
        elif key < list[mid]:
            last = mid - 1
    return -1

list1 = []  # Create an empty list
print("Create a list by entering elements in ascending order")
print("press enter after each element, press -999 to stop")
num = int(input())
while num!=-999:
    list1.append(num)
    num = int(input())
n = int(input("Enter the key to be searched: "))
pos = binarySearch(list1,n)
if(pos != -1):
    print(n,"is found at position", pos+1)
else:
    print(n,"is not found in the list")

Sample Output 1:

Create a list by entering elements in ascending order
press enter after each element, press -999 to stop
1
3
4
5
-999 …