Binary Search of an unsorted list

If you want the index from the unsorted list and you have to use binary search, try the following steps:

1. assign an index to each item in the unsorted list
2. sort the list
3. run the binary search
4. return the index that is associated with the found item

Binary search does only work on a sorted list, so there is no way around sorting it somewhere in the process if you need to use that search algorithm.

You need to sort a copy of the list, and maintain a list of indices back to the original list.

One way to do this is to use the decorate-sort-undecorate idiom:

>>> values = [5, 2, 7]
>>> decorated = list(zip(value, range(len(values))))
>>> sorted_decorated = sorted(decorated)
>>> sorted_values, indices = list(zip(sorted_decorated))
>>> sorted_values
[2, 5, 7]
>>> indices
[1, 0, 2]

Then you can do your binary search on the sorted values, and you have the mapping of the indices back to the original.

You can use the bisect module to implement binary search:

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

Using it:

>>> index(sorted_values, 5)
1

So the original index is:

>>> indices[1]
0

I think it is not very effective way. My implementation is here.

class Node(object):
 def __init__(self, index, value):
 self.index = index
 self.value = value
def binary_search(numbers, item):
 if len(numbers) == 0:
 return False
 else:
 middle = len(numbers) // 2
 if numbers[middle].value == item:
 return numbers[middle].index
 else:
 if item < numbers[middle].value:
 return binary_search(numbers[:middle], item)
 else:
 return binary_search(numbers[middle + 1:], item)
 unsorted_elems = [12, 2, 1, 5, 3, 7, 9]
 elems = []
 i = 0
 for elem in unsorted_elems:
 elems.append(Node(i, elem))
 i += 1
 elems = sorted(elems, key=lambda x: x.value)
 print(binary_search(elems, 1000)) //False
 print(binary_search(elems, 2)) // 1

• python
• binary-search