What is Binary Search?
This is a search algorithm which is quicker for large data sets ( a large array). For example if you were looking for a word in a dictionary. One disadvantage is that to make it work ( like a dictionary) the array must be sorted.
Binary is more efficient than a linear search as it will find an item quicker than linear search. This is because it involves fewer comparisons. It works by repeatedly checking the middle value of an array against the a target item. Each time the item is not found the array by discarding the half that doesn't contain the item. This is a bit like looking for a word in a dictionary.
Binary is more efficient than a linear search as it will find an item quicker than linear search. This is because it involves fewer comparisons. It works by repeatedly checking the middle value of an array against the a target item. Each time the item is not found the array by discarding the half that doesn't contain the item. This is a bit like looking for a word in a dictionary.
Binary Search - Dictionary example.
Imagine you were looking for the word nepotism in an english dictionary which has one word per page. You perform the following steps.
Open the dictionary in the middle.
If the item is found. Great we are done.
Otherwise is the word displayed earlier or later in than our search word?
Say the word on the middle page is "parrot" we know that's after, so we need to check the beginning half of the dictionary. So let's set the end value to the middle - 1.
Say the word on the middle page is "giraffe", we know that's before, so need to check the end half of the dictionnary. So let's set the beginning value to the middle + 1.
Open the dictionary in the middle.
If the item is found. Great we are done.
Otherwise is the word displayed earlier or later in than our search word?
Say the word on the middle page is "parrot" we know that's after, so we need to check the beginning half of the dictionary. So let's set the end value to the middle - 1.
Say the word on the middle page is "giraffe", we know that's before, so need to check the end half of the dictionnary. So let's set the beginning value to the middle + 1.
The Binary Search Algorithm
Set beginning as the first index which is 0.
Set end as the end of the array. while the beginning hasn't passed the end To find the middle set middle to ( begin + end ) / 2 If the the value at the middle position matches the search value. We have found it and can stop. Otherwise if the value at the middle position is too big focus on the first half by moving the end position to one before the middle. otherwise focus on the last half by moving the beginning position to one after the middle. |
*The middle is basically length dividided by two. However set middle as ( begin + end ) / 2 in case begin is changed to search the latter half of the array.while the beginning hasn't passed the end.
** We set mid to either mid -1 or mid +1 because we have already checked the value at mid, so we don't need to check it again. |
Coding the Binary Search
Here is the code using the pseudocode above as comments.
Find out more
Check BBCBitesize by clicking here.
|
|