how to write a linear search?

[qqabb]

im a beginner of coding and using python.
Im trying to code for a linear search but I don't know how to:(

[Gribouillis]

The list class 'index' method performs a linear search

>>> mylist = list("hello world")
>>> print(mylist)
['h', 'e', 'l', 'l', 'o', ' ', 'w', 'o', 'r', 'l', 'd']
>>> mylist.index('w')
6
>>> mylist[6]
'w'
>>> mylist.index('z')
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: list.index(x): x not in list

This also works for str objects (strings)

>>> mystr = "hello world"
>>> mystr.index('w')
6
>>> mystr.index('z')
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: substring not found

[ultimatebuster]

First of all, why linear search? That's like the worst algorithm to use ever.

But if you don't want to use the Python internal algorithm, a for loop can do it:

def findValue(v, li):
    for i in len(li):
        if v == len[i]:
            return i
    return -1

But that's such a bad algorithm. Internally, you have this -> value in li Also, you can code your own "smart" algorithm, like i did here:

def average(number1, number2):
    return sum([number1, number2])/2

def bisectFind(li, item):
    midpoint = (len(li)-1)/2
    minIndex = 0
    maxIndex = len(li)-1
    while True:
        if maxIndex - minIndex < 11:
            for i in range(minIndex,maxIndex+1):
                if li[i] == item:
                    return i
            return None
        if item < li[midpoint]:
            maxIndex = midpoint
            midpoint = average(minIndex, maxIndex)
            continue
        elif item > li[midpoint]:
            minIndex = midpoint
            midpoint = average(minIndex, maxIndex)
            continue
        elif item == li[midpoint]:
            return midpoint

[Gribouillis]

First of all, why linear search? That's like the worst algorithm to use ever.

But if you don't want to use the Python internal algorithm, a for loop can do it:

def findValue(v, li):
    for i in len(li):
        if v == len[i]:
            return i
    return -1

But that's such a bad algorithm. Internally, you have this -> value in li Also, you can code your own "smart" algorithm, like i did here:

def average(number1, number2):
    return sum([number1, number2])/2

def bisectFind(li, item):
    midpoint = (len(li)-1)/2
    minIndex = 0
    maxIndex = len(li)-1
    while True:
        if maxIndex - minIndex < 11:
            for i in range(minIndex,maxIndex+1):
                if li[i] == item:
                    return i
            return None
        if item < li[midpoint]:
            maxIndex = midpoint
            midpoint = average(minIndex, maxIndex)
            continue
        elif item > li[midpoint]:
            minIndex = midpoint
            midpoint = average(minIndex, maxIndex)
            continue
        elif item == li[midpoint]:
            return midpoint

Binary search works only if the list is initially sorted.

[ultimatebuster]

yeah that's true too. I actually didn't figure out how it works until a couple minutes ago. Wrote this a long time ago and didn't put a comment.

[vegaseat]

A linear search goes through a sequence of items one item at a time from the start of the sequence until the item is found ...

sequence = 'abcdefghijklmnopqrstuvwxyz'
search = 'z'
for c in sequence:
    if c == search:
        print("found search item")
        break

As you can see, if you were looking for 'a' it would be very efficient, but if you were looking for 'z' it would be the least efficient. If the size of your sequence is relatively small, a linear search is okay. However, imagine a sequence of a million or more items and your search item is near the end.

[-ordi-]

def binary_search(a, n, required):
      start = 0		
      end = n - 1	
      answer = 0
      while start <= end:
	    middle = (end + start) / 2
	    if a[middle] == required:
		  answer = middle
		  break
	    else:
		if required < a[middle]:
		  end = middle - 1
		else:
		  start = middle + 1
      return answer
	
array = (1, 2, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14)
print binary_search(array, len(array), 4)

slightly faster,
Requires array sorting!

[TrustyTony]

I would little clean up -ordi- code:

def binary_search(a, required):
    start = 0     
    end = len(a) - 1   
    answer = None
    while start <= end:
        middle = (end + start) / 2
        if a[middle] == required:
          answer = middle
          break
        elif required < a[middle]:
          end = middle - 1
        else:
          start = middle + 1
    return answer
    
array = (1, 2, 4, 5, 6, 7, 8, 10, 11, 12, 13, 14)

print binary_search(array, 9) ## not there
print binary_search(array, 4) ## index 2