BINARY SEARCH: Binary search method is very fast and efficient. This method requires that the list of elements be in sorted order. Binary search cannot be applied on an unsorted list. The data item to be searched is compared with the approximate middle entry of the list. If it matches with the middle entry, then the position is returned. If the data item to be searched is lesser than the middle entry, then it is compared with the middle entry of the first half of the list and procedure is repeated on the first half until the required item is found. If the data item is greater than the middle entry, then it is compared with the middle entry of the second half of the list and procedure is repeated on the second half until the required item is found. This process continues until the desired number is found or the search interval becomes empty. Algorithm: Procedure BINARYSEARCH( A, N, K, P ) / A is the array containing the list of data items / N is the number of data items in the list / K is the data item to be searched / P is the position where the data item is found Lower 0, Upper N – 1, P -1 While Lower ≤ Upper Mid (Lower + Upper) / 2 If K = A [Mid] Then P Mid Exit Loop Else If K < A[Mid] Then Upper Upper -1 Else Lower Lower + 1 End If End If End While End BINARYSEARCH In Binary Search algorithm given above, A is the list of data items containing N data items. K is the data item, which is to be searched in A. P is a variable used to indicate, at what position the data item is found. If the data item to be searched is found then the position where it is found is stored in P. If the data item to be searched is not found then -1 is stored in P, which will indicate the user, that the data item is not found. Initially P is assumed -1, lower is assumed 0 to point the first element in the list and upper is assumed as upper -1 to point the last element in the list. The mid position of the list is calculated and K is compared with A[mid]. If K is found equal to A[mid] then the value mid is assigned to P, the control comes out of the loop and the procedure comes to an end. If K is found lesser than A[mid], then upper is assigned mid – 1, to search only in the first half of the list. If K is found greater than A[mid], then lower is assigned mid + 1, to search only in the second half of the list. This process is continued until the element searched is found or the search interval becomes empty. Example: K Number to be searched: 40 U -Upper L -Lower M - Mid i = 0 i =1 i = 2 i = 3 i = 4 i = 5 i = 6 i = 7 i = 8 i = 9 1 22 35 40 43 56 75 83 90 98 L =0 M = 4 U = 9 K < A[4]U = 4 – 1 = 3 1 22 35 40 43 56 75 83 90 98 L = 0 M = 1 U = 3 K > A[1]L = 1 + 1 = 2 1 22 35 40 43 56 75 83 90 98 L, M = 2 U = 3 K > A [2]L = 2 + 1 = 3 1 22 35 40 43 56 83 90 98 L, M, U = 3 K = A[3] P = 3 : Number found at position 3 Advantages: • Searches several times faster than the linear search. • In each iteration, it reduces the number of elements to be searched from n to n/2. Disadvantages: • Binary search can be applied only on a sorted list.

BINARY SEARCH:

Binary search method is very fast and efficient. This method requires that the list of elements be in sorted order. Binary search cannot be applied on an unsorted list.

The data item to be searched is compared with the approximate middle entry of the list. If it matches with the middle entry, then the position is returned. If the data item to be searched is lesser than the middle entry, then it is compared with the middle entry of the first half of the list and procedure is repeated on the first half until the required item is found. If the data item is greater than the middle entry, then it is compared with the middle entry of the second half of the list and procedure is repeated on the second half until the required item is found. This process continues until the desired number is found or the search interval becomes empty.

Algorithm:

Procedure BINARYSEARCH( A, N, K, P ) / A is the array containing the list of data items / N is the number of data items in the list / K is the data item to be searched / P is the position where the data item is found Lower 0, Upper N – 1, P -1 While Lower ≤ Upper Mid (Lower + Upper) / 2 If K = A [Mid] Then P Mid Exit Loop Else If K < A[Mid] Then Upper Upper -1 Else Lower Lower + 1 End If End If End While End BINARYSEARCH

In Binary Search algorithm given above, A is the list of data items containing N data items. K is the data item, which is to be searched in A. P is a variable used to indicate, at what position the data item is found. If the data item to be searched is found then the position where it is found is stored in P. If the data item to be searched is not found then -1 is stored in P, which will indicate the user, that the data item is not found.

Initially P is assumed -1, lower is assumed 0 to point the first element in the list and upper is assumed as upper -1 to point the last element in the list. The mid position of the list is calculated and K is compared with A[mid]. If K is found equal to A[mid] then the value mid is assigned to P, the control comes out of the loop and the procedure comes to an end. If K is found lesser than A[mid], then upper is assigned mid – 1, to search only in the first half of the list. If K is found greater than A[mid], then lower is assigned mid + 1, to search only in the second half of the list. This process is continued until the element searched is found or the search interval becomes empty.

Example:

K Number to be searched: 40

U -Upper

L -Lower

M - Mid

i = 0     i =1     i = 2     i = 3        i = 4     i = 5       i = 6       i = 7      i = 8      i = 9
1	22		35	40	43	56	75	83	90	98
L =0					M = 4					U = 9
K <  A[4]U = 4 – 1 = 3
1	22		35	40	43	56	75	83	90	98
L = 0	M = 1			U = 3
K > A[1]L = 1 + 1 = 2
1	22		35	40	43	56	75	83	90	98
L, M = 2			U = 3
K > A [2]L = 2 + 1 = 3

1

22

35

40

43

56

83

90

98

L, M, U = 3

K = A[3] P = 3 :  Number found at position 3

Advantages:

• Searches several times faster than the linear search.

• In each iteration, it reduces the number of elements to be searched from n to n/2.

Disadvantages:

• Binary search can be applied only on a sorted list.