Answered # how to write a linear search?

Gribouillis 1,313 ultimatebuster 14 Featured Reply Gribouillis 1,313 ultimatebuster 14 vegaseat 1,720 Featured Reply -ordi- 6 Featured Reply pyTony 888 Write a C program that should create a 10 element array of random integers (0 to 9). The program should total all of the numbers in the odd positions of the array and compare them with the total of the numbers in the even positions of the array and indicate ...

0

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
```

*Edited 6 Years Ago by Gribouillis*: n/a

0

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
```

1

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.

0

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.

0

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.

*Edited 6 Years Ago by vegaseat*: least

1

```
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!

*Edited 6 Years Ago by -ordi-*: n/a

1

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
```

This question has already been answered. Start a new discussion instead.

Recommended Articles

Hi. so this is actually a continuation from another question of mineHere but i was advised to start a new thread as the original question was already answered.

This is the result of previous question answered :

code for the listbox - datagridview interaction

At the top of the code ...

the function that I created to find the ...