How to Implement Sequential And Binary Search Using Python

In this article, you will learn about implementation of vaious alorithms for searching. Based on Python operators we will see that we can make use of membership operator in to check if a value exists in a list or not.

This is nothing but searching for an element in a list. We will examine how to search element and improve process efficiency. We start by learning about Sequential Search.

The simplest way of searching for an element in a sequence is to check every element one by one. If the search finds the elements, it ends and returns the elements, otherwise, the search continues until the end of the sequence. This method of searching is known as linear search or sequential search. It follows a simple approach but it is quite inefficient way of searching for an element because we move from one element to the other right from beginning to end dand if the element is not present in the sequence we would not know about it till we reach the last element.

How to Implement Sequential Search Using Python

This is how you can implement the sequential search:

• The function takes two values: seq_list which is the list and target_num which is the number to search in the list.
• We set search_flag = 0 if the target number is found in the list we will set the search_flag to 1 else we let it be 0.
• We iterate through the list comparing each element in the list with the target_num.
• If a match is found we print a message and update the search_flag to 1.
• After the for loop if the search_flag is still 0 then it means that the number was not found.

def sequential_search(seq_list, target_num):
	search_flag = 0
	for i in range(len(seq_list)):
		if seq_list[i] == target_num:
			print("Found the target number ", target_num, "at index", i, ".")
			search_flag = 1

	if search_flag == 0:
		print("Target Number Does Not Exists. Search Unsuccessful")

Execution

seq_list = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]
target_num = input("Please enter the target number : ")
sequential_search(seq_list, int(target_num))

Output 1

Please enter the target number : 5
Found the target number  5 at index 4 .

Output 2

Please enter the target number : 2
Found the target number  2 at index 1 .

Output 3

Please enter the target number : 87
Target Number Does Not Exists. Search Unsuccessful

Implementation of Sequential Search For an Ordered List

When you sort element in a list, you often don’t need to scan the entire list. The moment we reach an element that has a value greater than the target number, we know that we need not to go any further.

Step 1

Define a function sequential_search() that takes two arguments – a list (seq_list) and the number that we are looking for (target_num).

Step 2

First, we define a flag (search_flag) and set it to “False” or “0”. The flag is set to “True” or “1” if the element is found. So, after traversing though the list if the search_flag value is still False of 0, we would know that the number that we are looking for does not exist in list.

def sequential_search(seq_list, target_num):
	search_flag = 0

Step 3

Now, it’s time to check the elements one by one so, we define the for loop:

def sequential_search(seq_list, target_num):
	search_flag = 0
	for i in range(len(seq_list)):

Step 4

We now define how to compare the elements. Since it is an ordered list for every i in seq_list we have to check if i > target_num. If yes, then it means that there is no point moving further as it is an ordered list, and we have reached an element that is greater than the number that we are looking for. However if seq_list[i] == target_num then, the search is successful and we can set the search_flag to 1.

def sequential_search(seq_list, target_num):
	search_flag = 0
	for i in range(len(seq_list)):
		if seq_list[i] > target_num:
			print("Search no further")
			break;
		elif seq_list[i] == target_num:
			print("Found the target number ", target_num, "at index", i, ".")
			search_flag = 1

Step 5

After the for loop has been executed if the value of search_flag is still 0 then a message stating that the target number was not found must be displayed.

Code

def sequential_search(seq_list, target_num):
	search_flag = 0
	for i in range(len(seq_list)):
		if seq_list[i] > target_num:
			print("Search no further")
			break;
		elif seq_list[i] == target_num:
			print("Found the target number ", target_num, "at index", i, ".")
			search_flag = 1

	if search_flag == 0:
		print("Target Number Does Not Exists. Search Unsuccessful")

Execution

seq_list = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]
target_num = input("Please enter the target number : ")
sequential_search(seq_list, int(target_num))

Output 1

Please enter the target number : 2
Found the target number  2 at index 1 .
Search no further

Output 2

Please enter the target number : 8
Found the target number  8 at index 7 .
Search no further

Output 3

Please enter the target number : 89
Target Number Does Not Exists. Search Unsuccessful

How to Implement Binary Search Using Python

In Binary Search, we locate a target value from a sorted list. The search begins from the centre of the sequence. The elements at the center is not equal to the target number, so we compare it with the target number. If the target number is greater than the elements at the center, we need to search for the number in the right half of the list and ignore the left half. Similarly, if the target number is less than the element present in the centre then we will have to direct our search efforts toward the left. Repeat this process until you complete the search. The beauty of binary search is that each search operation cuts the sequence in half and shifts focus to the half that might contain the value.

Implement binary search function

You can implement the binary search in the following manner:

Step 1: Define the binary_search function. It takes four parameters:

• sorted_list: The input list that is in sorted form.
• target_num: The number that we are looking for.
• starting_point: The place from where we want to start searching, default value=0.
• end_point: The end point for search, default value = None.

Note that the process splits the list in half at every step, so the starting and ending points may change with each search operation.

def binary_search(sorted_list, target_num, start_point=0, end_point=None):

Step 2: Do the following

• Set the search_flag to “False”
• If the end_point is not provided, it would have the default vslue of “None”, set it to the length of the input list.

def binary_search(sorted_list, target_num, start_point=0, end_point=None):
    search_flag = False
    if end_point == None:
        end_point = len(sorted_list)-1

Step 3: Check, the start_point should be less than the end point. If that is true, do the following:

• Get midpoint index value: mid_point = (end_point + start_point)//2
• Check the value of the element at mid_point. Is it equal to the target_num?
  • If sorted_list[mid_point] == target_num?
  • Set search_flag to True
• If not check if value at mid_point is greater than target_num:
  • sorted_list[mid_point] > target_num
  • If yes, then we can discard the right side of the list now we can repeat search from beginning to mid_point – 1 value. Set end point to mid_point – 1. The starting point can remain the same(0).
  • The function should now call itself with:
    • sorted_list : Same as before
    • target_num : Same as before
    • starting_point : Same as before
    • end_point: mid_point – 1
• If not check if value at mid_point is lesser than target_num:
  • sorted_list[mid_point] < target_num
  • If yes, then left side of the list is not required. We can repeat search from mid_point+1 to end of the list. Set starting point to mid_point+1. The ending_point can remain the same.
  • The function should now call itself with:
    • sorted_list : Same as before
    • target_num : Same as before
    • starting_point : mid_point+1
    • end_point : Same as before
• If at the end of this procedure the search_flag is still set to “False”, then it means that the value does not exist in the list.

Code

def binary_search(sorted_list, target_num, start_point=0, end_point=None):
    search_flag = False
    if end_point == None:
        end_point = len(sorted_list)-1
    if start_point < end_point:
        mid_point = (end_point + start_point)//2

        if sorted_list[mid_point] == target_num:
            search_flag = True

            print(target_num, "Exists in the list at ", sorted_list.index(target_num))
        elif sorted_list[mid_point] > target_num:
            end_point = mid_point - 1
            binary_search(sorted_list, target_num, start_point, end_point)

        elif sorted_list[mid_point] < target_num:
            start_point = mid_point+1
            binary_search(sorted_list, target_num, start_point, end_point)

    elif not search_flag:
        print(target_num, "Value does not exist")

Execution

sorted_list = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13]

binary_search(sorted_list, 14)

binary_search(sorted_list, 0)

binary_search(sorted_list, 5)

Output

14 Value does not exist
0 Value does not exist
5 Exists in the list at  4

Note: Some the sections below refer to time complexity. If you do not have knowledge of B-O notation then please refer the Appendix given at the end of the book.

Queue Data Structure Implementation Using Python