NIOS Computer Science: Chapter 11 – Array Computer Part 3

Download PDF of This Page (Size: 351K)

Image of binary search and sorted array

Image of Binary Search and Sorted Array

Image of binary search and sorted array

(ii) Binary search

This method requires the array to be either in ascending or descending order.

This method calculates the mid location form initial and final locations and compares the data with the value present in mid location.

Consider the case where the list is in ascending order

If data is less than a [mid] then data is present in the upper half otherwise data is present in the lower half.

The value of either final or initial will be changed. The mid value is calculated again and searching continues till the data is found or initial is greater than final.

The value of initial, final and mid for searching a value of 35 in an ascending order sorted list containing 9 elements is shown below:

/ / Binary search

# include < iostream.h >

const int N = 9;

void main ( )

{

int A[N], l, initial, final, mid, data;

cout < < “Enter nine values in ascending order”;

for (l = 0; l < N; l ++)

cin >> A [l];

cout << “Enter data to be searched”;

cin >> data;

initial = 0;

final = N - 1;

mid = (initial + final) / 2;

While (initial < = final) & & (A[mid]! = data))

{

if (A [mid] > data)

final = mid - 1;

else

initial = mid + 1;

}

if (A [mid] = = data)

cout << “data is present”;

if (initial > final)

cout <<“data not present in the list”;

}

The advantage of Binary search is that each search cuts the list in to half. A list of

10,000 names can be searched in just 12 searches.