Python Solutions
Solution 1 - Python
bisect_left
finds the first position p
at which an element could be inserted in a given sorted range while maintaining the sorted order. That will be the position of x
if x
exists in the range. If p
is the past-the-end position, x
wasn't found. Otherwise, we can test to see if x
is there to see if x
was found.
from bisect import bisect_left
def binary_search(a, x, lo=0, hi=None):
if hi is None: hi = len(a)
pos = bisect_left(a, x, lo, hi)
return pos if pos != hi and a[pos] == x else -1
Solution 2 - Python
Why not look at the code for bisect_left/right and adapt it to suit your purpose.
like this:
def binary_search(a, x, lo=0, hi=None):
if hi is None:
hi = len(a)
while lo < hi:
mid = (lo+hi)//2
midval = a[mid]
if midval < x:
lo = mid+1
elif midval > x:
hi = mid
else:
return mid
return -1
Solution 3 - Python
This is a little off-topic (since Moe's answer seems complete to the OP's question), but it might be worth looking at the complexity for your whole procedure from end to end. If you're storing thing in a sorted lists (which is where a binary search would help), and then just checking for existence, you're incurring (worst-case, unless specified):
Sorted Lists
- O( n log n) to initially create the list (if it's unsorted data. O(n), if it's sorted )
- O( log n) lookups (this is the binary search part)
- O( n ) insert / delete (might be O(1) or O(log n) average case, depending on your pattern)
Whereas with a set()
, you're incurring
- O(n) to create
- O(1) lookup
- O(1) insert / delete
The thing a sorted list really gets you are "next", "previous", and "ranges" (including inserting or deleting ranges), which are O(1) or O(|range|), given a starting index. If you aren't using those sorts of operations often, then storing as sets, and sorting for display might be a better deal overall. set()
incurs very little additional overhead in python.
Solution 4 - Python
Solution 5 - Python
Simplest is to use bisect and check one position back to see if the item is there:
def binary_search(a,x,lo=0,hi=-1):
i = bisect(a,x,lo,hi)
if i == 0:
return -1
elif a[i-1] == x:
return i-1
else:
return -1
Solution 6 - Python
This is right from the manual:
http://docs.python.org/2/library/bisect.html
8.5.1. Searching Sorted Lists
The above bisect() functions are useful for finding insertion points but can be tricky or awkward to use for common searching tasks. The following five functions show how to transform them into the standard lookups for sorted lists:
def index(a, x):
'Locate the leftmost value exactly equal to x'
i = bisect_left(a, x)
if i != len(a) and a[i] == x:
return i
raise ValueError
So with the slight modification your code should be:
def index(a, x):
'Locate the leftmost value exactly equal to x'
i = bisect_left(a, x)
if i != len(a) and a[i] == x:
return i
return -1
Solution 7 - Python
This one is:
- not recursive (which makes it more memory-efficient than most recursive approaches)
- actually working
- fast since it runs without any unnecessary if's and conditions
- based on a mathematical assertion that the floor of (low + high)/2 is always smaller than high where low is the lower limit and high is the upper limit.
def binsearch(t, key, low = 0, high = len(t) - 1):
while low < high:
mid = (low + high)//2
if t[mid] < key:
low = mid + 1
else:
high = mid
return low if t[low] == key else -1
Solution 8 - Python
I agree that @DaveAbrahams's answer using the bisect module is the correct approach. He did not mention one important detail in his answer.
From the docs bisect.bisect_left(a, x, lo=0, hi=len(a))
The bisection module does not require the search array to be precomputed ahead of time. You can just present the endpoints to the bisect.bisect_left
instead of it using the defaults of 0
and len(a)
.
Even more important for my use, looking for a value X such that the error of a given function is minimized. To do that, I needed a way to have the bisect_left's algorithm call my computation instead. This is really simple.
Just provide an object that defines __getitem__
as a
For example, we could use the bisect algorithm to find a square root with arbitrary precision!
import bisect
class sqrt_array(object):
def __init__(self, digits):
self.precision = float(10**(digits))
def __getitem__(self, key):
return (key/self.precision)**2.0
sa = sqrt_array(4)
index = bisect.bisect_left(sa, 7, 0, 10*10**4)
print 7**0.5
print index/(10**4.0)
Solution 9 - Python
If you just want to see if it's present, try turning the list into a dict:
l = [n*n for n in range(1000)]
d = dict((x, 1) for x in l)
count = 0
for n in range(1000000):
if n in d:
count += 1
On my machine, "if n in l" took 37 seconds, while "if n in d" took 0.4 seconds.
Solution 10 - Python
Dave Abrahams' solution is good. Although I have would have done it minimalistic:
def binary_search(L, x):
i = bisect.bisect_left(L, x)
if i == len(L) or L[i] != x:
return -1
return i
Solution 11 - Python
While there's no explicit binary search algorithm in Python, there is a module - bisect
- designed to find the insertion point for an element in a sorted list using a binary search. This can be "tricked" into performing a binary search. The biggest advantage of this is the same advantage most library code has - it's high-performing, well-tested and just works (binary searches in particular can be quite difficult to implement successfully - particularly if edge cases aren't carefully considered).
Basic Types
For basic types like Strings or ints it's pretty easy - all you need is the bisect
module and a sorted list:
>>> import bisect
>>> names = ['bender', 'fry', 'leela', 'nibbler', 'zoidberg']
>>> bisect.bisect_left(names, 'fry')
1
>>> keyword = 'fry'
>>> x = bisect.bisect_left(names, keyword)
>>> names[x] == keyword
True
>>> keyword = 'arnie'
>>> x = bisect.bisect_left(names, keyword)
>>> names[x] == keyword
False
You can also use this to find duplicates:
...
>>> names = ['bender', 'fry', 'fry', 'fry', 'leela', 'nibbler', 'zoidberg']
>>> keyword = 'fry'
>>> leftIndex = bisect.bisect_left(names, keyword)
>>> rightIndex = bisect.bisect_right(names, keyword)
>>> names[leftIndex:rightIndex]
['fry', 'fry', 'fry']
Obviously you could just return the index rather than the value at that index if desired.
Objects
For custom types or objects, things are a little bit trickier: you have to make sure to implement rich comparison methods to get bisect to compare correctly.
>>> import bisect
>>> class Tag(object):
... def __init__(self, tag):
... self.tag = tag
... def __lt__(self, other):
... return self.tag < other.tag
... def __gt__(self, other):
... return self.tag > other.tag
...
>>> tags = [Tag('bender'), Tag('fry'), Tag('leela'), Tag('nibbler'), Tag('zoidbe
rg')]
>>> key = Tag('fry')
>>> leftIndex = bisect.bisect_left(tags, key)
>>> rightIndex = bisect.bisect_right(tags, key)
>>> print([tag.tag for tag in tags[leftIndex:rightIndex]])
['fry']
This should work in at least Python 2.7 -> 3.3
Solution 12 - Python
Using a dict wouldn't like double your memory usage unless the objects you're storing are really tiny, since the values are only pointers to the actual objects:
>>> a = 'foo'
>>> b = [a]
>>> c = [a]
>>> b[0] is c[0]
True
In that example, 'foo' is only stored once. Does that make a difference for you? And exactly how many items are we talking about anyway?
Solution 13 - Python
This code works with integer lists in a recursive way. Looks for the simplest case scenario, which is: list length less than 2. It means the answer is already there and a test is performed to check for the correct answer.
If not, a middle value is set and tested to be the correct, if not bisection is performed by calling again the function, but setting middle value as the upper or lower limit, by shifting it to the left or right
def binary_search(intList, intValue, lowValue, highValue):
if(highValue - lowValue) < 2:
return intList[lowValue] == intValue or intList[highValue] == intValue
middleValue = lowValue + ((highValue - lowValue)/2)
if intList[middleValue] == intValue:
return True
if intList[middleValue] > intValue:
return binary_search(intList, intValue, lowValue, middleValue - 1)
return binary_search(intList, intValue, middleValue + 1, highValue)
Solution 14 - Python
Check out the examples on Wikipedia http://en.wikipedia.org/wiki/Binary_search_algorithm
def binary_search(a, key, imin=0, imax=None):
if imax is None:
imax = len(a) - 1
while imin <= imax:
mid = (imin + imax)//2
midval = a[mid]
if midval < key:
imin = mid + 1
elif midval > key:
imax = mid - 1
else:
return mid
raise ValueError
Solution 15 - Python
'''
Only used if set your position as global
'''
position
def bst(array,taget):
global position
low = 0
high = len(array)
while low <= high:
mid = (lo+hi)//2
if a[mid] == target:
position = mid
return -1
elif a[mid] < target:
high = mid+1
else:
low = mid-1
return -1
I guess this is much better and effective. please correct me :) . Thank you
Solution 16 - Python
-
s
is a list.
-
binary(s, 0, len(s) - 1, find)
is the initial call.
-
Function returns an index of the queried item. If there is no such item it returns -1
.
def binary(s,p,q,find):
if find==s[(p+q)/2]:
return (p+q)/2
elif p==q-1 or p==q:
if find==s[q]:
return q
else:
return -1
elif find < s[(p+q)/2]:
return binary(s,p,(p+q)/2,find)
elif find > s[(p+q)/2]:
return binary(s,(p+q)/2+1,q,find)
Solution 17 - Python
I needed binary search in python and generic for Django models. In Django models, one model can have foreign key to another model and I wanted to perform some search on the retrieved models objects. I wrote following function you can use this.
def binary_search(values, key, lo=0, hi=None, length=None, cmp=None):
"""
This is a binary search function which search for given key in values.
This is very generic since values and key can be of different type.
If they are of different type then caller must specify `cmp` function to
perform a comparison between key and values' item.
:param values: List of items in which key has to be search
:param key: search key
:param lo: start index to begin search
:param hi: end index where search will be performed
:param length: length of values
:param cmp: a comparator function which can be used to compare key and values
:return: -1 if key is not found else index
"""
assert type(values[0]) == type(key) or cmp, "can't be compared"
assert not (hi and length), "`hi`, `length` both can't be specified at the same time"
lo = lo
if not lo:
lo = 0
if hi:
hi = hi
elif length:
hi = length - 1
else:
hi = len(values) - 1
while lo <= hi:
mid = lo + (hi - lo) // 2
if not cmp:
if values[mid] == key:
return mid
if values[mid] < key:
lo = mid + 1
else:
hi = mid - 1
else:
val = cmp(values[mid], key)
if val == 0:
return mid
if val < 0:
lo = mid + 1
else:
hi = mid - 1
return -1
Solution 18 - Python
def binary_search_length_of_a_list(single_method_list):
index = 0
first = 0
last = 1
while True:
mid = ((first + last) // 2)
if not single_method_list.get(index):
break
index = mid + 1
first = index
last = index + 1
return mid
Solution 19 - Python
Binary Search :
def binarySearch(list, searchItem, size, upperBound, lowerBound):
print(list)
print(upperBound)
print(lowerBound)
mid = ((upperBound + lowerBound))
print(mid)
if int(list[int(mid)]) == value:
return "value exist"
elif int(list[int(mid)]) < value:
return searchItem(list, value, size, upperBound, mid + 1)
elif int(list[int(mid)]) > value:
return searchItem(list, value, size, mid - 1, lowerBound)
// To call above function use :
list = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
searchItem = 1
print(searchItem(list[0], item, len(list[0]) -1, len(list[0]) - 1, 0))
Solution 20 - Python
Many good solutions above but I haven't seen a simple (KISS keep it simple (cause I'm) stupid use of the Python built in/generic bisect function to do a binary search. With a bit of code around the bisect function, I think I have an example below where I have tested all cases for a small string array of names. Some of the above solutions allude to/say this, but hopefully the simple code below will help anyone confused like I was.
Python bisect is used to indicate where to insert an a new value/search item into a sorted list. The below code which uses bisect_left which will return the index of the hit if the search item in the list/array is found (Note bisect and bisect_right will return the index of the element after the hit or match as the insertion point) If not found, bisect_left will return an index to the next item in the sorted list which will not == the search value. The only other case is where the search item would go at the end of the list where the index returned would be beyond the end of the list/array, and which in the code below the early exit by Python with "and" logic handles. (first condition False Python does not check subsequent conditions)
#Code
from bisect import bisect_left
names=["Adam","Donny","Jalan","Zach","Zayed"]
search=""
lenNames = len(names)
while search !="none":
search =input("Enter name to search for or 'none' to terminate program:")
if search == "none":
break
i = bisect_left(names,search)
print(i) # show index returned by Python bisect_left
if i < (lenNames) and names[i] == search:
print(names[i],"found") #return True - if function
else:
print(search,"not found") #return False – if function
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
Solution 21 - Python
Hello here is my python implementation without bisect. let me know if it can be improved.
def bisectLeft(a, t):
lo = 0
hi = len(a) - 1
ans = None
while lo <= hi:
mid = (lo + hi) // 2
if a[mid] < t:
lo = mid + 1
elif a[mid] > t:
hi = mid - 1
elif a[mid] == t:
if mid == 0: return 0
if a[mid-1] != t: return mid
hi = mid - 1
return ans
def bisectRight(a, t):
lo = 0
hi = len(a) - 1
ans = None
while lo <= hi:
mid = (lo + hi) // 2
if a[mid] == t:
ans = mid
if a[mid] <= t:
lo = mid + 1
else:
hi = mid - 1
return ans