0

Hi so the goal here is to improve the number of steps needed to find an element in a list using Sequential Search.

So I have an unsorted List numbers = [5, 2, 1, 0, 3] and i'm trying to find lets say element 3. It takes 5 steps to find it.

My task here is to create a new function called sortedSequentialSearch() that takes in a sorted list in ascending order and improve it to reduce the steps needed to find element 3.

Here's my code for the normal Sequential Search:

def sequentialSearch(theValues, target):
    n = len(theValues)
    count = 0 

    for i in range(n):
        count = count + 1
        if theValues[i] == target:
            print(f"Found, {count} steps needed")
            return True
    return False

How can I improve this if I lets say pass in numbers.sort() ?

petezurich
  • 9,280
  • 9
  • 43
  • 57
SunAwtCanvas
  • 1,261
  • 1
  • 13
  • 38

3 Answers3

1

You can use binary search after sorting the array. It has log(n) time complexity.

In this case 2.3 steps, which is better than 3.

https://www.geeksforgeeks.org/binary-search/

Abhishek Verma
  • 1,671
  • 1
  • 8
  • 12
0

One efficient way to search a sorted array is binary search. I modified your code to use it:

def binary_search(theValues, target, lower_bound, upper_bound):
    middle = (upper_bound + lower_bound) // 2

    if theValues[middle] == target:
        return True
    elif upper_bound <= lower_bound:
        return False
    elif target > theValues[middle]:
        return binary_search(theValues, target, middle + 1, upper_bound)
    else:
        return binary_search(theValues, target, lower_bound, middle - 1)

Another option is interpolation search. This algorithm is more efficient than binary search if the numbers are uniformly distributed, averaging log(log(n)) time. It's worst case isn't as good though, because it can take O(n) time if the numbers change exponentially.

Daniel Giger
  • 2,023
  • 21
  • 20
0

If the numbers are sorted you do not have to continue the search once you have reached an element greater than the value of the element you are trying to find

def sequentialSearch(theValues, target):
  n = len(theValues)
  count = 0 

  for i in range(n):
    count = count + 1
    if theValues[i] == target:
        print(f"Found, {count} steps needed")
        return True
    if theValues[i] > target:
        return False
  return False
jibsonline
  • 1