472,805 Members | 2,194 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes and contribute your articles to a community of 472,805 developers and data experts.

Binary Search Algorithm

176 Expert 100+
One commonly used algorithm is the binary search.
If you don't already know it, you should read on.
Very helpful. Saves much CPU. Reduces computations exponentially.

When searching though a lot of information to find a match, the first idea that comes to mind is the linear search. Loop through all the values looking for a match. If you find it, return the location, or value and end the search.
However this becomes highly inefficient when the values to be searched become very large. It's a O(N) algorithm. At worse case you may have to search ALL the values to find a match, or even worse find that it's not there!

If the list of items can be sorted numerically or ASCII. Use a binary search!

First, sort the list.Then compare the value in the very center (round up or down in case of uneven list elements) to your search term. If it is "less than" your term, you know that it must be lower than that point. So you can eliminate the upper range. If the term has a greater value than your center point value, eliminate the lower range.

Thus reducing the amount of items to be searched by half.

Apply this technique to the remaining items continually and reduce the search by half each iteration.

Thus running at the much faster O(log N) algorithm.


Warning: uses "recursion", remember to consider function call loads on CPU. In some languages this can actually be slower than linear. See non recursive below.
(taken from Wikipedia)

Expand|Select|Wrap|Line Numbers
  1. BinarySearch(A[0..N-1], value, low, high) {
  2.        if (high < low)
  3.            return -1 // not found
  4.        mid = low + ((high - low) / 2)  // Note: not (low + high) / 2 !!
  5.        if (A[mid] > value)
  6.            return BinarySearch(A, value, low, mid-1)
  7.        else if (A[mid] < value)
  8.            return BinarySearch(A, value, mid+1, high)
  9.        else
  10.            return mid // found
  11.    }
There is an optimization here.
Sometimes when dealing with large numbers, or floating point high precision.
mid = (low + high)/2
can overflow and hog memory, resulting in unreliable results.
mid = low + ((high - low)/2)
fixes it. :)
See here...

Non Recursive:
Expand|Select|Wrap|Line Numbers
  1. low = 0
  2.        high = N
  3.        while (low < high) {
  4.            mid = low + ((high - low) / 2)  // Note: not (low + high) / 2 !!
  5.            if (A[mid] < value)
  6.                low = mid + 1; 
  7.            else
  8.                 //can't be high = mid-1: here A[mid] >= value,
  9.                 //so high can't be < mid if A[mid] == value
  10.                 high = mid; 
  11.        }
  12.        // high == low, using high or low depends on taste 
  13.        if ((low < N) && (A[low] == value))
  14.            return low // found
  15.        else
  16.            return -1 // not found      

There are MANY sources for this most elementary algorithm. Just type "binary search" into Google.

Happy coding....
Mar 31 '09 #1
6 11993
6,050 Expert 4TB
I'd never thought of doing it like that.

Thanks a bunch :D
Apr 9 '09 #2
11,448 Expert 8TB
Also see Fibonacci Search for a slightly better search than the binary search method.

kind regards,

Jun 16 '09 #3
6,050 Expert 4TB
While we're talking about search algorithms, the boyer-moore algorithm is interesting.
Jun 16 '09 #4
176 Expert 100+
Nice, I had never heard of the Fibonacci search myself.

Very interesting...
Jun 16 '09 #5
in researching the Fibonacci search code i also noticed the golden ratio search.
what do you think about this alternative?
Sep 11 '09 #6
2,057 Expert 2GB
? The golden ratio search appears to be a mathematical search based on unknown secondary values. I don't see how that applies in terms of searching for a particular item within an array.

The Fibonacci search reminds me of a priority heap.

Re the original binary search:
We should note that if we're ever only going to search once or twice through this array, sorting is not that useful. It becomes much more useful when we are repeatedly searching through this array.

To be honest, I find the low + ((high - low) / 2) to be a waste in this case, requiring an extra operation. You're dealing with integers, and unless the number of elements reaches INT_MAX/2, you don't really need to use it. As stated before, this is more of a floating point addition concern. Further, if concerned about speed you should use >> 1 instead of / 2.
If you get to the point where you are actually reaching extremely large numbers of elements, you may want to consider a Interpolation search (sometimes called a dictionary search), until you reach a certain smaller range, or provide subkeys for ranges.
Mar 22 '10 #7

Sign in to post your reply or Sign up for a free account.

Similar topics

by: Alex Gerdemann | last post by:
Hello, I am writing a program where I have a vector (std::vector<std:string> list) that I need to search many times. To accomplish this efficiently, I plan to sort the list using...
by: Tarique Jawed | last post by:
Alright I needed some help regarding a removal of a binary search tree. Yes its for a class, and yes I have tried working on it on my own, so no patronizing please. I have most of the code working,...
by: joshc | last post by:
If I have an array of data that I know to be sorted in increasing order, and the array is less than 50 elements, and I want to find the first element greater than a certain value, is a simple...
by: willamette3597 | last post by:
Could Someone tell me Where can I get The result though the Binary Search eg. max , min , mid ,want; While ( max > min ) { mid = (min + max )/2 ; if ( mid > want ) max = mid + 1; else min =...
by: Peter Schmitz | last post by:
Hi, one of the main task of my currently developed application is to search in small buffers for given patterns (average buffer size 1000 bytes). Now, for some reasons I can't use the provided C...
by: free2cric | last post by:
Hi, I have a single link list which is sorted. structure of which is like typedef struct mylist { int num; struct mylist *next;
by: Bob Rock | last post by:
Hello, I have an array of strings and need to find the matching one with the fastest possible code. I decided to order the array and then write a binary search algo. What I came up with is the...
by: phanipep | last post by:
When is the binary search used for searching in a list? Give the binary search algorithm. Compare the performance of binary search with linear search?
by: Channveer | last post by:
how to write the C code in Linux to find the time taken by the binary search algorithm ?
by: erikbower65 | last post by:
Using CodiumAI's pr-agent is simple and powerful. Follow these steps: 1. Install CodiumAI CLI: Ensure Node.js is installed, then run 'npm install -g codiumai' in the terminal. 2. Connect to...
by: erikbower65 | last post by:
Here's a concise step-by-step guide for manually installing IntelliJ IDEA: 1. Download: Visit the official JetBrains website and download the IntelliJ IDEA Community or Ultimate edition based on...
by: kcodez | last post by:
As a H5 game development enthusiast, I recently wrote a very interesting little game - Toy Claw ((http://claw.kjeek.com/))。Here I will summarize and share the development experience here, and hope it...
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Sept 2023 starting at 18:00 UK time (6PM UTC+1) and finishing at about 19:15 (7.15PM) The start time is equivalent to 19:00 (7PM) in Central...
by: Taofi | last post by:
I try to insert a new record but the error message says the number of query names and destination fields are not the same This are my field names ID, Budgeted, Actual, Status and Differences ...
by: DJRhino1175 | last post by:
When I run this code I get an error, its Run-time error# 424 Object required...This is my first attempt at doing something like this. I test the entire code and it worked until I added this - If...
by: Rina0 | last post by:
I am looking for a Python code to find the longest common subsequence of two strings. I found this blog post that describes the length of longest common subsequence problem and provides a solution in...
by: lllomh | last post by:
How does React native implement an English player?
by: DJRhino | last post by:
Was curious if anyone else was having this same issue or not.... I was just Up/Down graded to windows 11 and now my access combo boxes are not acting right. With win 10 I could start typing...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.