Home | JSP | EJB | JDBC | Java Servlets | WAP  | Free JSP Hosting  | Spring Framework | Web Services | BioInformatics | Java Server Faces | Jboss 3.0 tutorial | Hibernate 3.0 | XML

Tutorial Categories: Ajax | Articles | JSP | Bioinformatics | Database | Free Books | Hibernate | J2EE | J2ME | Java | JavaScript | JDBC | JMS | Linux | MS Technology | PHP | RMI | Web-Services | Servlets | Struts | UML


 

Java Tutorials


 

 

Struts Tutorials

Struts Resources

Visit Forum! Post Questions!
Jobs At RoseIndia.net!

Java Notes: Algorithms: Binary Search

[an error occurred while processing this directive]

Divide in half

A fast way to search a sorted array is to use a binary search. The idea is to look at the element in the middle. If the key is equal to that, the search is finished. If the key is less than the middle element, do a binary search on the first half. If it's greater, do a binary search of the second half.

Performance

The advantage of a binary search over a linear search is astounding for large numbers. For an array of a million elements, binary search, O(log N), will find the target element with a worst case of only 20 comparisons. Linear search, O(N), on average will take 500,000 comparisons to find the element. Probably the only faster kind of search uses hashing, a topic that isn't covered in these notes.

This performance comes at a price - the array must be sorted first. Because sorting isn't a fast operation, it may not be worth the effort to sort when there are only a few searches.

Example

  1 
  2 
  3 
  4 
  5 
  6 
  7 
  8 
  9 
 10 
 11 
 12 
 13 
 14 
 15 
 16 
 17 
 18 
 19 
 20 
 21 
 22 
 23 
 24 
 25 
 26 
/** Binary search of sorted array.  Negative value on search failure.
 *  The upperbound index is not included in the search.
 *  This is to be consistent with the way Java in general expresses ranges.
 *  The performance is O(log N).
 *  @param sorted Array of sorted values to be searched.
 *  @param first Index of beginning of range.  First element is a[first].
 *  @param upto  Last element that is searched is sorted[upto-1].
 *  @param key   Value that is being looked for.
 *  @return      Returns index of the first match, or or -insertion_position 
 *               -1 if key is not in the array. This value can easily be
 *               transformed into the position to insert it.
 */
public static int binarySearch(int[] sorted, int first, int upto, int key) {
    
    while (first < upto) {
        int mid = (first + upto) / 2;  // Compute mid point.
        if (key < sorted[mid]) {
            upto = mid;     // repeat search in bottom half.
        } else if (key > sorted[mid]) {
            first = mid + 1;  // Repeat search in top half.
        } else {
            return mid;     // Found it. return position
        }
    }
    return -(first + 1);    // Failed to find key
}

Related Pages

Linear Search, Recursive Binary Search
Ask programming questions?

 

 

Add This Tutorial To:
  Del.icio.us   Digg   Google   Spurl   Blink   Furl   Simpy   Y! MyWeb 

Current Comments

3 comments so far (post your own) View All Comments Latest 10 Comments:

no relavent examples

Posted by prasad on Sunday, 12.6.09 @ 18:21pm | #93120

Performance
The advantage of a binary search over a linear search is astounding for large numbers. For an array of a million elements, binary search, O(log N), will find the target element with a worst case of only 20 comparisons. Linear search, O(N), on average will take 500,000 comparisons to find the element. Probably the only faster kind of search uses hashing, a topic that isn't covered in these notes.

This performance comes at a price - the array must be sorted first. Because sorting isn't a fast operation, it may not be worth the effort to sort when there are only a few searches.
Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26



/** Binary search of sorted array. Negative value on search failure.
* The upperbound index is not included in the search.
* This is to be consistent with the way Java in general expresses ranges.
* The performance is O(log N).
* @param sorted Array of sorted values to be searched.
* @param first Index of beginning of range. First element is a[first].
* @param upto Last element that is searched is sorted[upto-1].
* @param key Value that is being looked for.
* @return Returns index of the first match, or or -insertion_position
* -1 if key is not in the array. This value can easily be
* transformed into the position to insert it.
*/
public static int binarySearch(int[] sorted, int first, int upto, int key) {

while (first < upto) {
int mid = (first + upto) / 2; // Compute mid point.
if (key < sorted[mid]) {
upto = mid; // repeat search in bottom half.
} else if (key > sorted[mid]) {
first = mid + 1; // Repeat search in top half.
} else {
return mid; // Found it. return position
}
}
return -(first + 1); // Failed to find key
}

Posted by Earl Joel on Thursday, 11.27.08 @ 02:11am | #82096

Performance
The advantage of a binary search over a linear search is astounding for large numbers. For an array of a million elements, binary search, O(log N), will find the target element with a worst case of only 20 comparisons. Linear search, O(N), on average will take 500,000 comparisons to find the element. Probably the only faster kind of search uses hashing, a topic that isn't covered in these notes.

This performance comes at a price - the array must be sorted first. Because sorting isn't a fast operation, it may not be worth the effort to sort when there are only a few searches.
Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26



/** Binary search of sorted array. Negative value on search failure.
* The upperbound index is not included in the search.
* This is to be consistent with the way Java in general expresses ranges.
* The performance is O(log N).
* @param sorted Array of sorted values to be searched.
* @param first Index of beginning of range. First element is a[first].
* @param upto Last element that is searched is sorted[upto-1].
* @param key Value that is being looked for.
* @return Returns index of the first match, or or -insertion_position
* -1 if key is not in the array. This value can easily be
* transformed into the position to insert it.
*/
public static int binarySearch(int[] sorted, int first, int upto, int key) {

while (first < upto) {
int mid = (first + upto) / 2; // Compute mid point.
if (key < sorted[mid]) {
upto = mid; // repeat search in bottom half.
} else if (key > sorted[mid]) {
first = mid + 1; // Repeat search in top half.
} else {
return mid; // Found it. return position
}
}
return -(first + 1); // Failed to find key
}

Posted by Earl Joel on Thursday, 11.27.08 @ 02:09am | #82095

  JDO Tutorials
  EAI Articles
  Struts Tutorials
  Java Tutorials
  Java Certification

Tell A Friend
Your Friend Name

 

 
Browse all Java Tutorials
Java JSP Struts Servlets Hibernate XML
Ajax JDBC EJB MySQL JavaScript JSF
Maven2 Tutorial JEE5 Tutorial Java Threading Tutorial Photoshop Tutorials Linux Technology
Technology Revolutions Eclipse Spring Tutorial Bioinformatics Tutorials Tools SQL
 

Home | JSP | EJB | JDBC | Java Servlets | WAP  | Free JSP Hosting  | Search Engine | News Archive | Jboss 3.0 tutorial | Free Linux CD's | Forum | Blogs

About Us | Advertising On RoseIndia.net  | Site Map

India News

Send your comments, Suggestions or Queries regarding this site at roseindia_net@yahoo.com.

Copyright 2007. All rights reserved.

[an error occurred while processing this directive]