Binary Search algorithm is applied where we want to search number in sorted numbers. In this algorithm, first to find mid position of the list and divide the list into two parts. If number is equal to mid then position find easily , this is the best case of binary search.
Problem: Design an algorithm to search a number using binary search technique.
Input : A list (array) of numbers in ascending order, number of elements in the list and key to search.
Output: Returns 1 if the key is found otherwise returns 0
BIN_SEARCH(LIST, N, KEY)
[LIST is an array of numbers in ascending order]
[N is the size of the array and KEY is the number to search]
L <-- 0; H<-- N-1; [Assuming that array index start from 0]
M <-- INT ( (L+H) /2 ) [Get the quotient or integer part after division]
Repeat While (L <= H)
If(Key == LIST[M]) then:
Return 1 [Key found]
Else:
If(Key < LIST[M] ) then:
H <-- M-1 [Move to the left half of the list]
Else:
H <-- M+1 [Move to the right half of the list]
[End of If]
[End of If]
[End of While]
Return 0 [Key not found]
Exit.
Problem: Design an algorithm to search a number using binary search technique.
Input : A list (array) of numbers in ascending order, number of elements in the list and key to search.
Output: Returns 1 if the key is found otherwise returns 0
BIN_SEARCH(LIST, N, KEY)
[LIST is an array of numbers in ascending order]
[N is the size of the array and KEY is the number to search]
L <-- 0; H<-- N-1; [Assuming that array index start from 0]
M <-- INT ( (L+H) /2 ) [Get the quotient or integer part after division]
Repeat While (L <= H)
If(Key == LIST[M]) then:
Return 1 [Key found]
Else:
If(Key < LIST[M] ) then:
H <-- M-1 [Move to the left half of the list]
Else:
H <-- M+1 [Move to the right half of the list]
[End of If]
[End of If]
[End of While]
Return 0 [Key not found]
Exit.