BinarySearch algorithm is search algorithm in the sorted data set.
it can not apply to unsorted data set.
Let’s take a look step by step. assume the data set is already ascending sorted.
First, Check the middle of data set.
Compare middle to target number.
.
if the middle is larger than target, we don’t need to take care about right side of middle.
find the middle in the left part.
repeat until find the target number.
we can implement this by two way. using recursive function or while statement.
resursive function
def binarySearch(arr, left, right, target):
if right >= left: # if the data set is descending
if right >= left:
mid = left + (right - left)/2
if arr[mid] == target:
return mid
elif arr[mid] > target:
return binarySearch(arr, left, mid-1, target)
else:
return binarySearch(arr, mid+1, right, target)
else:
return -1
arr = [ 1, 2, 3, 4, 5, 6, 7, 8 ]
target = 1
result = binarySearch(arr, 0, len(arr)-1, target)
if result != -1:
print "Element is present at index %d" % result
else:
print "Element is not present in array"
while statement
def binarySearch(arr, left, right, target):
if right >= left:
while right >= left:
mid = left + (right - left)/2
if arr[mid] == target:
return mid
elif arr[mid] > target:
right = mid - 1
else:
left = mid + 1
else:
return -1
arr = [ 1, 2, 3, 4, 5, 6, 7, 8 ]
target = 1
result = binarySearch(arr, 0, len(arr)-1, target)
if result != -1:
print "Element is present at index %d" % result
else:
print "Element is not present in array"
you can see the result using the IDEONE
next time, we will take a binary search tree.
Thank you.
