Binary
Search
· Binary
search is used to find an item from a sorted list of items.
· In
this type of search, a sorted array by
repeatedly dividing the search interval in half.
· Begin
with an interval covering the whole array If the value of the search key is
less than the item in the middle of the interval, narrow the interval to the
lower half Otherwise narrow it to the upper half.
· Repeatedly
check until the value is found or the interval is empty.
In this post we will learn basic of the linear
search using three steps:
1. Algorithm
2.Pseudo Code
3. Code
1.Algorithm
Step 1:Compare x with the middle element
Step 2:If x matches with middle element, we return
the mid index
Step 3:Else If x is greater than the mid
element, then x can only lie in right half
Subarray after the mid element. So we recur for right half
Step 4:Else (x is smaller) recur for the left
half.
2.Pseudo
Code
Procedure binarysearch
A->sorted array
n ->size of array
X->value to be searched
Set lowerBound = l
Set upperBound =n
while x not
found
if
upperBound < lowerBound
EXIT: x does not ex ists .
set
midPoint = lowerBound + ( upperBound lowerBound ) / 2
if
A[midPoint] < x
set lowerBound midPoint+1
if
AfmidPotnt] > x
set upperBound = midPoint-1
if
A[midPoint ] = x
EXIT:x found at location midPoint
end while
end procedure
|
3.Code
def
binary_search(arr, x):
low = 0
high = len(arr) - 1
mid = 0
while low <= high:
mid = (high + low) // 2
if arr[mid] < x:
low = mid + 1
elif arr[mid] > x:
high = mid - 1
else:
return mid
return -1
arr = [ 2, 3, 4, 10,
40 ]
x = 10
result =
binary_search(arr, x)
if result != -1:
print("Element is present at
index", str(result))
else:
print("Element is not present in
array")
|
Output:-
0 Comments