What is the process of binary search?

Answer 1

1. //ALGORITHM:Bin search(a,i,l,x).

2. //given an array a(i,l) of elements in non-decreasing.

3.// order,1<=i<=l,determine wether x is present and

4. //if so,return j such that x=a[j],else return 0.

5. {

6. if(l=i) then

{

if(x=a[i] then return i;

else return 0;

}

else

{

mid=[(i+l)/2]

if(x-a[mid] then return mid

else if(x<a[mid]) then

return Bin search(a,i,mid-1,x)

else return Bin search(a.mid+1,l,x)

}

}

Answer 2

The process of binary search involves choosing the midpoint in a list of ordered elements, determining if that is the answer, or if it is above or below the answer. The process iterates on successively half sized sets until the answer is found or the set size is zero, meaning the answer was not found.

In an array based structure, pointers or indices are used starting at the ends of the array, and they are walked inwards by half of the remaining size towards each other.

In a tree based structure, the midpoints are already known - they are the nodes in the tree - and the process is simply to walk down the tree, choosing left or right at each iteration, until you either find the element or find the case of no subsequent node.

Answer 3

A binary search works by halving the sorted list.

In the first iteration the center most element is compared with search data.

This will determine if what is being looked for in the upper or lower half of the list.

Now only half the list needs to be searched.

The process is now repeated and that the remaining part of the list to be searched is cut in half again.

This process continues until there is a match and the data or pointer to the data is returned, or the list can not be halved further this indicates a match was not found.

A binary search is quite fast because very few iterations are required to fully search a large list.

Taking 65535 as the number of records in the list.

1st iteration brings the part of the list to be searched down to 32767

2nd iteration 16383

3rd iteration 8191

4th iteration 4095

5th iteration 2047

6th iteration 1023

7th iteration 511

8th iteration 255

9th iteration 127

10th iteration 63

11th iteration 31

12th iteration 15

13th iteration 7

14th iteration 3

15th iteration 1

16th iteration 0. If there is no match at this point then what we are searching for is not in the list.

Small list are better searched sequentially and need not be sorted order. I understand that small lists can be quite large before a binary search will be a benefit but I have never empirically tested.

Answer 4

A non-recursive binary search is an iterative binary search. Both methods use a divide-and-conquer algorithm to eliminate half of a sorted array until the value being sought is found in the midpoint of the reduced array, or the upper bound crosses the lower bound of the array in which case the value does not exist. Thus the function will either return the index of the midpoint or it will return -1 to indicate the value does not exist.

A recursive binary search is a function that accepts an array, a lower and upper bound of the array, and the value being sought. If the upper bound is less than the lower bound, then the value being sought does not exist so the function returns -1. Otherwise, if the element in the middle of the upper and lower bound contains the value, then its index is returned (the value has been found). But if the value being sought is less than the middle element's value, then the index of the element that precedes the middle element becomes the upper bound, otherwise the index of the element that follows the middle element becomes the lower bound. The function then calls itself with these reduced bounds, effectively eliminating half of the array, and returns the value returned by that call (which may itself invoke more recursions).

An iterative function does the same thing but it doesn't call itself recursively. Instead, it accepts an array, the number of elements in the array and the value being sought from which it calculates the lower and upper bounds (initially the entire array) and the midpoint. It then begins an iterative loop until the upper bound crosses the lower bound, returning -1. Upon each iteration, if the value of the element at the midpoint is the same as the value being sought, the midpoint is returned. If the value is less than the midpoint value, the upper bound is adjusted, otherwise the lower bound is adjust, a new midpoint is determined and the loop continues for another iteration.

Of the two, the iterative method is faster because it completely eliminates all the recursive function calls. Every function call is an expensive overhead, and the larger the array, the more recursive calls there are likely to be. Indeed, this is a classic example of a function that can be implemented iteratively and recursively and, whenever there is a choice, the iterative method is the method of choice, even if the code isn't quite as elegant.

The following example (in C++) demonstrates the differences in the actual implementation:

#include <iostream>

// iterative binary search

int ibsearch(int * haystack, int length, int needle)

{

int lower = 0, upper = length-1, mid = upper / 2;

while( upper >= lower )

{

if( haystack[mid] -1 )

printf( "Needle %d was not found\n", needle );

else

printf( "Needle %d was found at index %d\n", needle, index );

}

printf( "\n" );

return(0);

}

Answer 5

In order to perform a binary search you must first sort all the elements to be searched. You must also use a container that supports random access. In other words, you must use an array. Although you can use a binary tree, this is less efficient than an array because of the need to store the links between elements; an array requires no links between elements and thus offers the most compact storage possible.

Once the set has been sorted into an array, you can use the binary search algorithm:

1) Given the lower and upper bound of an array, determine the index of the middle element.

2) If the indexed element holds the value your are searching for, return the index.

3) If the indexed element is larger than the element being sought then set the upper bound to index-1, otherwise set the lower bound to index+1.

4) If the lower bound is greater than the upper bound, the value does not exist. Return -1 to indicate failure.

5) Goto 1.

Note that step 3 reduces the set by half each time the value is not found.

Answer 6

The binary search algorithm can be implemented efficiently using a sorted array. We begin our search with the middle element in the array. If that element holds the value we're looking for we are done; the value exists and we can return true. However, if that element does not hold our value, we compare the values. If the element value is too low, we know that our value must be in the right half of the array, otherwise it must be in the left half of the array, so we repeat the process with that portion of the array, gradually reducing the number of elements we need to search by half each time. Eventually, we will either find our value or the remaining half of the array will be empty, in which case the value does not exist and we can return false.

The following example demonstrates how we can implement a binary search for an array of type int. Note how we use a half-closed range of iterators to keep track of the sub-array (initially the whole array). As is common with all algorithms that operate upon a range, the end iterator refers to the "one-past-the-end" of the range (hence it is half-closed).

// search the half-closed range [begin:end) for value using binary search algorithm

// returns true of the value exists, otherwise false

bool binary_search (int* begin, int* end, int value) {

std::ptrdiff_t count {begin-end};

if (count<0) return false; // the range is invalid

while (count) {

int* mid {begin+(count/2)}; // refer to middle element of range

if (*mid==value) return true; // the value was found

// if we reach this point, the value was not found so reduce the range by half

if (*mid<value) {

begin = mid + 1; // the value must be in the range beginning at mid+1

} else {

end = mid; // the value must be in range ending at mid

count = begin-end; // update the count

}

return false; // the value does not exist

}

Given this implementation, we can invoke it as follows:

int x[10] {2, 4, 6, 8, 10, 12, 14, 16, 18, 20}; // a sorted array

int* begin {x};

int* end {begin + 10}; // one past the end

assert (binary_search (begin, end, 4)); // assert existing value exists

assert (!binary_search (begin, end, 11)); // assert non-existent value does not exist