Ch3-Search algorithm for coding test

ConfidenceCoding

10 min readOct 9, 2023

Search algorithms

1.Sequential search

2.Binary search

3.Tree Data structure

4.Binary search tree

Q1.Searching parts

Q2.Slicing cucumber

1.Sequential search

Sequential search is the method for checking elemesnts in list from starting portion to end portion one by one in order. Normally, it is used when you search the data in unsorted list. The postitive point is it can search the data no mattter how much there are. Following example is process of searching data for finding letter ‘peter’.

step0. initialize datas

step1. check the first element. ‘james’ is no data what we want to find so go to next element.

step2. check the second element. ‘tim’ is not data what we want to find so go to next element.

step3. check the third element. ‘peter’ is a data what we want to find. Finish the sequential searching.

Sequential searching is commomnly used when checking the specific element in the list and performing ‘count()’ method which is count the number of specific value. The code is like these.

def sequential_search(n, target, array):
    # check the element one by one
    for i in range(n):
        # If find the element what we want to find
        if array[i] == target:
            # return this porttion
            return i + 1

print('input the number of element and input the string what you want to find after space.')



input_data = input().split()
# number of element
n = int(input_data[0])
# the string what you want to find
target = input_data[1]

print('create the elements what you input before and split it by space')
array = input().split()

# print the result
print(sequential_search(n, target, array))

2.Binary search

Binary search use three parameters that is first portion, end portion and middle portion. this algorithm get the result by repeatly comparing datas which are first portion and middle portion. it can be used when the datas are after being arranged and it is rubust algorithm when the datas are arranged. Following example is the process for finding number ‘4’ in the list consisted of ten datas.

step1. check first portion, end portion and middle portion. If middle portion is real number round up it. First portion is [0]. end portion is [9]. middle portion is [4] ( 4.5 is rounded up ). and then, compare element in middle point with number ‘4’ what you want to find. The data in middle portion is greater than ‘4’. So change the end portion as [3] where is previous index of [4].

step2. First portion is [0], end portion is [3], middle portion is [1]. the number ‘2’ is lesser than ‘4’. So change the first portion as [2].

step3. First portion is [2]. end portion is [3]. middle portion is [2] ( 2.5 is rounded up ). the element is in the middle portion is ‘4’ what you wanted to find. So stop the binary search.

Let’s make the sentence of these process

and then make the flow chart

this is code of binary search

def binary_search(array, target, start, end):
    while start <= end:
        mid = (start + end) // 2
        # return the index of middle 
        if array[mid] == target:
            return mid
      
        # check the left side if target is lesser than middle
        if array[mid] > target:
            end = mid - 1
    
        # check the right side if target is greater than middle
        if array[mid] < target:
            start = mid + 1
    return None


# input target(what you want to find element) and n (number of element)
n, target = list(map(int, input().split()))

# input whole element
array = list(map(int, input().split()))

# print the result of binary search
result = binary_search(array, target, 0, n-1)
if result == None:
    print("There is no element")
else:
    print(result + 1)


""" 
5 0
0 2 4 6 8
1
"""

you can make code by using recursive function

def binary_search(array, target, start, end):
    if start > end:
        return None
    mid = (start + end) // 2
    # return the index of middle
    if array[mid] == target:
        return mid

    # check the left side if target is lesser than middle
    elif array[mid] > target:
        return binary_search(array, target, start, mid-1)
    
    # check the right side if target is greater than middle
    else:
        return binary_search(array, target, mid+1, end)

You may think binary search code is simple but if there is no source code for reference, it is little bit tricky. Some senior programmer told it is not easy to make perfect binary search. Binary search combine with other algorithm in coding test competition. For example, you need to use greedy algorithm and binary search. So i recommend memorize this sort code.

3.Tree data structure

Datas in the database are always arranged by using algorithm which is like binary search. It is little bit different with binary search but it is similar and the speed of perfoming the process is fast. Tree datastructure is connected by node and node. Node is unit of information. it is commonly used in database system or file system for managing huge mount of data. There are some of princiapl features in tree data structure.

Tree is presented by parent node and child node.
Top of node in tree called by root node
Bottom of node in tree called by terminal node.
Sub tree is part of tree from origin tree
Tree is hyarchical like file system and it is suite for arraged data.

Most of software which manage big datas use tree data structure for storing datas and it is possible to search datas with fast speed when it use binary search.

3.Binary search tree

Get ConfidenceCoding’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

The basic tree data stucture is binary search tree which is developed for efficiently working binary search. Let’s look at following picture.

Binary search tree is like this picture but every tree is not binary search tree. It has following features.

Left child node is lesser than parent node.
Right child node is greater than parent node.

The principal is “ Left child node < Parent node < Right child node “. You might know 13 < 32 < 53 in the following picture.

The process iput datas and out datas in the binary search tree is closer to data structure than algorithm. Most questions in coding test require to searching data in the binary search tree. So i will mention about searching process. Following example is process for finding ’37’ in the tree.

step1. Binary search visit root node at first. Root node is ‘30’ and element we want to find is ‘37’. As the formula, Left child node is lesser than ‘30’ so we don’t need to check every element where in left side and visit right child node.

step2. ‘48’ is parent node in this time. ‘48’ is greater than ‘37’ so it visit left child node.

step3. the node it visited is same the value what we want to find.

We look at just 3 steps but if there are many node in tree, the process repeats same this process so it is enough if you understand these picture.

If the datas are over 10 million or size of searching range is over 100 billion in the question of coding test, ‘input()’ method is slow and you might get fail. You can use ‘readline()’ function in sys library for avoiding time over.

import sys
# Get the string data
input_data = sys.stdin.readline().rstrip()

print(input_data)

# Hello, world! => Hello, world!

You need to call ‘rstrip()’ method after get a line of string in sys library. Because space character is added after you use ‘readline()’ method.

Q1.Searching parts

There is the number of n parts in the electric shop. Customer request the quotation about parts of named ‘m’. Make the program that can check parts in the shop.

The parts number is like following example if there are 5 pcs.

N = 5
[8, 3, 7, 9, 2]

The parts number that customer request three part is like that.

M = 3
[5, 7, 9]

The program will print if there is part, it will show ‘yes’ or there isn’t part, it will show ‘no’ after checking.

Solution

There are few solution for this question. I will let you know binary search at the first time. Firstly, Sort the number of n parts in the shop. After then, you check the m parts that customer requested and you can use binary search.

def binary_search(array, target, start, end):
    while start <= end:
        mid = (start + end) // 2
        # return the index of middle 
        if array[mid] == target:
            return mid
      
        # check the left side if target is lesser than middle
        if array[mid] > target:
            end = mid - 1
    
        # check the right side if target is greater than middle
        if array[mid] < target:
            start = mid + 1
    return None



# input the n ( the number of parts ) 
n = int(input())

# input the parts number in the shop
array = list(map(int, input().split()))

# sort for binary search
array.sort()

# input the m ( the number of parts that customer requested )
m = int(input())

# input the parts number that customer requested
x = list(map(int, input().split()))


# print the result of binary search
for i in x:
    result = binary_search(array, i, 0, n-1)
if result != None:
    print("yes", end=' ')
else:
    print("no", end=' ')


"""
5
0 2 4 6 8
1
2
yes
"""

This question can be solved by using set data type. ‘set()’ method initialize the set data type and check the number what customer want to find.

# input the n ( the number of parts ) 
n = int(input())

# input the parts number in the shop
array = set(map(int, input().split()))

# input the parts number that customer requested
x = list(map(int, input().split()))

# check the part number what customer requested
for i in x:
    if i in array:
        print('yes', end=' ')
    else:
        print('no', end=' ')

"""
5
0 2 4 6 8
2
yes
"""

Q2.Slicing cucumber

You want to cut cucumber as same length. The cutter can can same length when you sent the height ( H ). If the cucumber is longer than H, it be cut top of part. For example, there are 19, 14, 10, 17 cm of cucumbers in a line and set the H as 15cm. After then the height of cucumber will be 15, 14, 10, 15cm. the length of cut part are 4, 0, 0, 2 cm. The customer will get 6cm. Make the program which print max height of cutter when customer ask length of cucumber ’n’ and put the number of cucumber ‘m’.

Solution

This question is type of parametric search. Parametric search is the method that can change optimization problem to decision problem which return ‘yes’ or ‘no’. The idea of solution is simple that it repeatedly change height ‘H’ until finding the result. So the condition is “ Is H meet the condition?” after then solve the problem by narrowing down the condition as satisfaction of conditions ( ‘yes’ or ‘no’ ). Let’s look at steps for finding ‘H’

step1. Set the starting portion is ‘0’ and end portion is ‘19’. If you set the middle portion as ‘9’ for ‘H’, sum of cucumber is ‘25’ ( = 10 + 6 + 1 + 8 ). The customer want to get ‘6 cm’ and ‘25’ is greater than ‘6’. So move the start portion to ‘10’ where is next to ‘9’.

step2. Start portion is ‘10'. End portion is ‘19’. Middle portion is ‘14’. If you set ‘H’ as ‘14’, sum of cucumber is ‘9’ ( = 5 + 1+ 3 ). ‘9’ is still greater than ‘6’ and move the start portion to ‘15’ where is next to ‘14’.

step3. Start portion is ‘15’. End portion is ‘19’. Middle portion is ‘17’. Sum of cucumber is ‘2’. ‘2’ is lesser than ‘6’ and move the end portion to ‘16’ where is next to ‘17’.

step4. Start portion is ‘15’. End portion is ‘16’. Middle portion is ‘15’. Sum of cucumber is ‘6’ ‘6’ is the number customer want to get.

You can use recursive function but it is more long code and repeat statement is more shorter than recursive function in parametric search problems. Here is source code.

# Input N ( number of cucumber ) , h( length of cucumber what customber want )
n, h = list(map(int, input().split(' ')))

# Input each height of cucumber
array = list(map(int, input().split()))

# Set the start portion and end portion
start = 0
end = max(array)

# Start binary search
result = 0
while(start <= end):
    total = 0
    mid = (start + end) // 2
   
    # sum of cucumber length 
    for x in array:
        if x > mid:
            total += x - mid
   
    # If H is greater than sum ( search left side ) 
    if total < h
        end = mid - 1

    # If H is lesser than sum ( search right side )
    else:
        result = mid
        start = mid + 1

print(result)