A binary search can be performed on an ordered array. It works by taking a value

that is being searched for and testing it by the element in the middle of the array. If

the value being searched for is lower than the item in the middle of the ordered

array, it can be determined that if the value exists, it is in the first half of the array.

If the value is larger than the element in the middle, the value might exist in the

upper half. Once the direction is known, half of that new section is tested to further

narrow down where the value can be. This is repeated until the value is found or

until there are no more elements left. The binary search gets its name from the fact

that the remaining elements are always split in half (binary equals 2). Because a binary search requires the elements to be in order, this algorithm cannot work for an unordered array since the

unordered array can be unpredictable in terms of item positions.

The binary search can eliminate large sections of an array in an effort to narrow

down the list to find the value, assuming it exits. When compared to the linear

search, this can result in a huge difference in performance as Ngrows larger. For example, an array being searched with a linear algorithm that is made up of 1 million

elements will take on average 500,000 steps for items that exist, which can mean

that some checks can go up to the whole million depending on the item. Using a

binary search on an ordered array with that same number of elements will take

20 comparisons. To go from an average of 500,000 comparisons to just 20 is a huge

difference. To go from 1 million comparisons to 20 with items that are not found

while(1)

{

current = (lowerBound + upperBound) >> 1;

if(m_array[current] == searchKey)

{

return current;

}

else if(lowerBound > upperBound)

{

return -1;

}

else

{

if(m_array[current] < searchKey)

lowerBound = current + 1;

else

upperBound = current - 1;

}

}

return -1;

}

};

The binary search starts off by defining the bounds that make up

the search range, which is initially set to the entire array. Once the range is set, the

middle of the range is determined and the element at the position is tested. If the

item is found, the index is returned; if the lower bound’s value becomes higher than

the upper bound’s value (which will happen when the search has stepped through

the entire array), then the value is not found. If neither of these two cases are true,

the lower bound, which is the minimum search range position, is adjusted if

the item is greater than the item in the middle, or else the upper bound is adjusted.

Adjusting the range values will quickly shrink the search range until the value is

found or until there are no more elements to check this

operation is pretty fast as N grows larger.

that is being searched for and testing it by the element in the middle of the array. If

the value being searched for is lower than the item in the middle of the ordered

array, it can be determined that if the value exists, it is in the first half of the array.

If the value is larger than the element in the middle, the value might exist in the

upper half. Once the direction is known, half of that new section is tested to further

narrow down where the value can be. This is repeated until the value is found or

until there are no more elements left. The binary search gets its name from the fact

that the remaining elements are always split in half (binary equals 2). Because a binary search requires the elements to be in order, this algorithm cannot work for an unordered array since the

unordered array can be unpredictable in terms of item positions.

The binary search can eliminate large sections of an array in an effort to narrow

down the list to find the value, assuming it exits. When compared to the linear

search, this can result in a huge difference in performance as Ngrows larger. For example, an array being searched with a linear algorithm that is made up of 1 million

elements will take on average 500,000 steps for items that exist, which can mean

that some checks can go up to the whole million depending on the item. Using a

binary search on an ordered array with that same number of elements will take

20 comparisons. To go from an average of 500,000 comparisons to just 20 is a huge

difference. To go from 1 million comparisons to 20 with items that are not found

while(1)

{

current = (lowerBound + upperBound) >> 1;

if(m_array[current] == searchKey)

{

return current;

}

else if(lowerBound > upperBound)

{

return -1;

}

else

{

if(m_array[current] < searchKey)

lowerBound = current + 1;

else

upperBound = current - 1;

}

}

return -1;

}

};

The binary search starts off by defining the bounds that make up

the search range, which is initially set to the entire array. Once the range is set, the

middle of the range is determined and the element at the position is tested. If the

item is found, the index is returned; if the lower bound’s value becomes higher than

the upper bound’s value (which will happen when the search has stepped through

the entire array), then the value is not found. If neither of these two cases are true,

the lower bound, which is the minimum search range position, is adjusted if

the item is greater than the item in the middle, or else the upper bound is adjusted.

Adjusting the range values will quickly shrink the search range until the value is

found or until there are no more elements to check this

operation is pretty fast as N grows larger.

## 0 comments:

## Post a Comment