Comment

Earl Joel
binary sort,
November 27, 2008 at 2:11 AM

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
}

View All Comments | View Tutorial
Related Tutorial and Articles
Design concepts & design patterns Questions

Algorithms
Algorithms  Java has default sort method(Collection.sort), Then why we still use various sorting algorithms

General

Java arraylist binarysearch
It is a method for searching the array element in the given array. It is a static method of the class Arrays. It uses the binary search... used in binarySearch must be sorted. binarsearch() method with Unsorted arrays

General

Introduction to Collection Algorithms
. The  Java platform provides great majority of the algorithms to perform... Introduction to Collection Algorithms       Algorithms: The Collections and Arrays classes

Java Interview Questions

multiplication algorithms in java divide and conquer
multiplication algorithms in java divide and conquer  I need multiplication algorithms in java divide and conquer ask from user input two numbers in binary then the program multiply two number use multiplication algorithm in java

Java Beginners

multiplication algorithms in java divide and conquer
multiplication algorithms in java divide and conquer  I need multiplication algorithms in java divide and conquer ask from user input two numbers in binary then the program multiply two number use multiplication algorithm in java

Java Beginners

multiplication algorithms in java divide and conquer
multiplication algorithms in java divide and conquer  I need multiplication algorithms in java divide and conquer ask from user input two numbers in binary then the program multiply two number use multiplication algorithm in java

Java Beginners

Sorting algorithms - Java Beginners
Sorting algorithms  I'v being given an assignment and I still couldn't find a proper answer for the following questions.Can anyone pls pls help me wi it? 1)Compare and contrast efficiencies of Shell,Quick,Heap and Radix sort

Java Beginners

Algorithms
Sorting Algorithms program in Java  I need to fix this problem- Write a program to measure the speed of the three sorting algorithms. program... the integer number of substitution process (bubble-sort). -The method

General

Java Array Binary Search example
Java Array Binary Search It is a method for searching the array element... example demonstrates how to do a binary search on the Java array object... the binary search algorithm.  It returns the index of the found element

Java Beginners

binary search - Java Beginners
binary search  Write a java program to search an array by using recursive binary search.  /* * To change this template, choose Tools...; /** * * @author Satish */ public class BinarySearch { public static final

Java Beginners

Sort
with this A program is required to ask users to rate the Java programming language... Scanner(System.in); System.out.print("Rate Java(0-10): "); int rate..."); } } } } System.out.print("Invalid! Rate Java within the range(0-10): "); rate=input.nextInt

Java Tips and Examples

Quick Sort in Java
Quick sort in Java is used to sort integer values of an array... in comparison to other sorting algorithms like bubble sort, insertion sort, heap... into a sorted array. Example of Quick Sort in Java: public class QuickSort

Java Beginners

java - Java Beginners
Search: http://www.roseindia.net/java/java-tips/algorithms/searching/linearsearch.shtml b)Binary Search: http://www.roseindia.net/java/java-tips...://www.roseindia.net/java/java-tips/algorithms/searching/rbinarysearch.shtml Along

JSP Servlet Questions

searching technique
searching technique  Hi, i need any searching technique in java to search the data and give the all possible data by links

Java Interview Questions

search and sort techniques in java
search and sort techniques in java  Hi i attened an interview recently... they asked to write all searching and sorting technique codes in java.. i... of all these searchings and sortings in java...please help... Regards, Anugnya

JavaScript Questions

searching problem
searching problem  how we can make a code in core java for searching in hard disk? i have to make an antivirus as my minor project , so i have need this type code to search the virus in hard disk

JavaScript Questions

searching problem
searching problem  how we can make a code in core java for searching in hard disk? i have to make an antivirus as my minor project , so i have need this type code to search the virus in hard disk

Java Beginners
General

Heap Sort in Java
Heap Sort in Java is used to sort integer values of an array. Like quicksort.... Example of Heap Sort in Java: public class eap_Sort{ public static void main...\sorting>Javac heap_Sort.java C:\array\sorting>java heap_Sort Heap Sort

Java Beginners

Send me Binary Search - Java Beginners
Send me Binary Search  how to use Binary think in java give me the Binary Search programm thx..  Hi friend, import java.io.... binarySearch(AnyType [] a, AnyType x ){ int low = 0; int high = a.length

General

Binary Search in Java
Binary Search in Java In this section, we are going to search an element from an array using Binary Search. The advantage of a binary search over a linear... java.util.*; public class BinarySearch { public static void main(String[] args

Java Interview Questions

Sorting and Searching
help me with this A program is required to ask users to rate the Java...) { Scanner input = new Scanner(System.in); System.out.print("Rate Java(0-10...! Rate Java within the range(0-10): "); rate=input.nextInt

Java Beginners

binary tree
://www.roseindia.net/java/java-get-example/java-binary-tree-code.shtml http://www.roseindia.net/java/java-get-example/java-binary-tree-insert.shtml...binary tree  can a binary tree be implemented with out comparing

Java Tips and Examples

Insertion Sort In Java
Insertion Sort In Java     .... There are more efficient algorithms such as quick sort, heap sort, or merge sort... In this example we are going to sort integer values of an array using insertion sort

Java Beginners

Binary Search - Java Beginners
Binary Search  how to use Binary think in java give me the Binary Search programm thx

Java Beginners

Java Sorting and Searching
Java Sorting and Searching   If anyone could help me with this I would be really thankful! Write a program that stores the names of these artists in a String array. The program should prompt the user to enter the name

Java Beginners

Java String searching.
Java String searching.  How to search a string in given String array?   import java.util.Scanner; public class StringSearch { public... and for searching we used userCity.equalsIgnoreCase(city[i

Java Beginners

java - Java Beginners
the following links: http://www.roseindia.net/java/java-tips/algorithms/searching/linearsearch.shtml http://www.roseindia.net/java/java-tips/algorithms/searching/binarysearch.shtml http://www.roseindia.net/java/java-tips/algorithms

Servlet Interview Questions

Searching operation in JAva
Searching operation in JAva  Sir, I have made a project for the Dispatch section of my office. I have to search for letters that are dispatched on a particular date. Now there are thousands of letters dispatched on a particular

Servlet Interview Questions

Searching operation in JAva
Searching operation in JAva  Sir, I have made a project for the Dispatch section of my office. I have to search for letters that are dispatched on a particular date. Now there are thousands of letters dispatched on a particular

Servlet Interview Questions

Searching operation in JAva
Searching operation in JAva  Sir, I have made a project for the Dispatch section of my office. I have to search for letters that are dispatched on a particular date. Now there are thousands of letters dispatched on a particular

Servlet Interview Questions

Searching operation in JAva
Searching operation in JAva  Sir, I have made a project for the Dispatch section of my office. I have to search for letters that are dispatched on a particular date. Now there are thousands of letters dispatched on a particular

Java-Tutorials

Quick Sort in Java
Quick Sort in Java Quick Sort in Java is used to sort elements of an array..., insertion sort, heap sort and other sorting algorithms. First it divides an array... in Java works? Quick Sort algorithm works on comparison sort that means

General

Insertion, sorting and searching in array
to perform searching and sorting in array. In the java code given below we have declare an array of integer type and then sort by using java.util.Arrays.Sort...; } Insertion, sorting and searching in array

Java Beginners

octal to binary
octal to binary  i want to know how to convert a octal to binary number   Here is a java example that converts octal to binary. import... binary=Integer.toBinaryString(i); System.out.println(binary

Design concepts & design patterns Questions

algorithms and data structures - Design concepts & design patterns
algorithms and data structures  write a java methods to implement queues by the simple but slow method of keeping the front of the queue always in the first position odf a linear array

Java Interview Questions

searching the string in a paragraph?
searching the string in a paragraph?  how to search a string in a paragraph and display the corresponding line number and position of a string in java

Java-Tutorials

Binary Search in Java
Binary Search in Java is used to search an element from an array. Programmers opt for Binary search over linear search when it comes to large numbers. It can... the answer "Not Found". Following is the example of Binary Search in Java: import

Java Interview Questions

insertion sort
insertion sort  write a program in java using insertion sort

Java Interview Questions

insertion sort
insertion sort  write a program in java using insertion sort

Java Interview Questions

bubble sort
bubble sort  write a program in java using bubble sort

Java Interview Questions

insertion sort
insertion sort  write a program in java using insertion sort

Java Interview Questions

insertion sort
insertion sort  write a program in java using insertion sort

General

Heap Sort in Java
Heap Sort in Java      ..._Sort.java C:\array\sorting>java heap_Sort Heap Sort... are going to sort integer values of an array using heap sort. There are two types

Java Beginners

Java read binary file  I want Java read binary file example code... at Reading binary file into byte array in Java. Thanks   Hi, There is many more examples at Java File - Learn how to handle files in Java with Examples

Java Beginners

BINARY TO DECIMAL - Java Beginners
BINARY TO DECIMAL  HELP ME PLSS. PROGRAM THAT CONVERTS BINARY TO DECIMAL  Hi friend, Program to convert Binary To Decimal : import... (System.in); System.out.print ("Enter a binary number "); String str

PHP Tutorial

php array binary search
PHP Binary Search Array is used to search the given value in the array. In php there is no function for the binary search like java or other language. User can implement and use the binary search in php as given below

Java Beginners

buble sort
buble sort  ascending order by using Bubble sort programm   Java BubbleSort Example

Java Interview Questions

Interview Tips - Java Interview Questions
Interview Tips  Hi, I am looking for a job in java/j2ee.plz give me interview tips. i mean topics which i should be strong and how to prepare. Looking for a job 3.5yrs experience

Java Beginners

java binary file io example
java binary file io example  java binary file io example

Java Beginners

SEARCH AND SORT
SEARCH AND SORT  Cam any one provide me the code in java that : Program to search for MAX,MIN and then SORT the set using any of the Divide and conquer method

Java Beginners

JAVA: Recusrion, Binary Search
JAVA: Recusrion, Binary Search  I want to learn about Binary Search... it using a recursive implementation of Binary Search. For the cases when more than one result can be returned, modify Binary Search to return all the elements

Java Beginners

Searching with alphabetical order - Java Beginners
Searching with alphabetical order  Hi, I want to this please help me Steps:- 1:-I have a one form of name text box with two button. 2:-user input in name text box(alphabetical order)search all fields from

Java Beginners

Binary to decimal - Java Beginners
Binary to decimal  Need help pls.. i cannot run this program... pls... = Integer.parseInt(JOptionPane.showInputDialog("Input Binary:")); String c = args[0...; String value = JOptionPane.showInputDialog("Input Binary"); int len

Java Beginners

Searching with alphabetical order - Java Beginners
Searching with alphabetical order  Hi, please understood my problem and send write code its very urgent I a write once again. Steps.... 2:-User input in the name text box(searching alphabetical order) name

Java Beginners

sort java - Java Beginners
sort java  1. A statistics company wants to keep information of families. The information of a family is the family name, the number of members and first name of each member. The families are sorted alphabetically by family name

Java Beginners

searching for strings in a file
searching for strings in a file  how can i search of a person and display the other details associated with the name using java gui window?  ...://www.roseindia.net/java/example/java/swing/addeditanddeleteemployee_inf.shtml

Java Beginners

Java insertion sort question
Java insertion sort question  I've got another program that I need help with. I am trying to write a Java method that accepts an array of strings, and sorts the strings using the insertion sort algorithm. Then I need to write

Java Beginners

Binary Search!!! - Java Beginners
Binary Search!!!  Hi Sir, My question is quite simple. im only getting "ArrayIndexOutOfBoundsException : 10" in the if statement which is inside the 1st while loop. How can i get rid of it? The if statement is btw

Java Beginners

bubble sort - Java Beginners
bubble sort  how to write program The bubble-sort algorithm in double...  Hi friend, Bubble Sort program : public class...[] = {10,5,3,89,110,120,1,8,2,12}; System.out.println("Values Before the sort:\n

Java Server Faces Questions

binary distributions - Java Server Faces Questions
binary distributions  what are binary distributions

Java Beginners

Searching a tex on a table in java! - Java Beginners
Searching a tex on a table in java!  i have a table which contains several data. using a textfield the item hat i search must be selected... the problem. For more information on Java visit to : http://www.roseindia.net

JavaScript Questions

Java: Searching a string from doc files
Java: Searching a string from doc files   I want to search a string from DOC, DOCX files in java. Can anyone please help me

Java Beginners

Java Dictionary-Sort,Extract
Java Dictionary-Sort,Extract  *I need to make an English(other language) dictionary by collecting english/other language words in a text file;then using that text file I need to sort the words collected in alphabetical order

Java Beginners

searching a text string in file - Java Beginners
searching a text string in file  code to match a string in a file that is already mentioned in java code.if the string matches any part of a string that whole string is printed

Java Beginners

Insertion Sort - Java Beginners
Insertion Sort  Hello rose india java experts.If you don't mind.Can you help me.What is the code for Insertion Sort and Selection Sort that displays...: public class InsertionSort { public static void sort(String[] array) { int

Java Beginners

array sort - Java Beginners
array sort  hi all, can anybody tell me how to sort an array without any in-built methods.   Hi Friend, Try the following code: public class SortArrayWithoutUsingMethod{ public static void sortArray(int

Java Beginners

heap sort in java
heap sort in java  plz modify this program so that it can take input as integers and string both..... public class heap_Sort{ public static void...("\n Heap Sort\n---------------\n"); System.out.println("\n Unsorted Array\n\n

General

Java Programming Tips, Articles and Notes
Java Programming Language simple tips to use Java effectively This section is not very structured and discussing the random topics of the Java Programming Language and which is useful in learning the Java Language. Java Programming

Java Beginners

hex to binary convertion in java - Java Beginners
hex to binary convertion in java  HI, im doin a application wch requires to send a binary message to other mobiles, so i need to convert the hex values to binary format.So the binary format could either be a ringtone

Java Beginners

hex to binary convertion in java - Java Beginners
hex to binary convertion in java  HI, im doin a application wch requires to send a binary message to other mobiles, so i need to convert the hex values to binary format.So the binary format could either be a ringtone

Java Beginners

hex to binary convertion in java - Java Beginners
hex to binary convertion in java  HI, im doin a application wch requires to send a binary message to other mobiles, so i need to convert the hex values to binary format.So the binary format could either be a ringtone

Java Code Examples

Java Convert Octal to Binary
Java Convert Octal to Binary In this tutorial, you will learn how to convert octal to binary. Java has provide different ways to change the number system of different numbers. You can convert and decimal to octal, decimal to binary

Java Tips and Examples

Merge Sort Java
Merge Sort in Java is used to sort integer values of an array. There are many methods to sort Java like bubble sort, insertion sort, selection sort, etc.... Example of Merge Sort in Java public class mergeSort{ public static void main

Programming Tutorials

JavaScript Array Binary Search
JavaScript Array Binary Search       The JavaScript Binary Search becomes very useful in case of large Arrays.  The Binary Search algorithm is used to  handle

General

Java binary to decimal
Java binary to decimal       This Tutorial helps you to know the code for Java binary... you in understanding a how to get a 'Java binary to decimal'. For this we have

JSP Servlet Questions

sort function - JSP-Servlet
sort function  How to sort a string variable in java   Hi friend, Please give in details and full source code to solve the problem. For information on java visit to : http://www.roseindia.net/java

Java Beginners

How to write in Binary file in Java programming language
How to write in Binary file in Java programming language  I need some help about Java programming. Please explain me "How to write in Binary file in Java programming language

Java Beginners

Insertion Sort Timer
Insertion Sort Timer  Welcome all I wanna program in java find the timer of insertion sort and find time complexity for random value thanks all

Java Tips and Examples

Conversion of Decimal to Binary in Java
Conversion of Decimal to Binary  in Java In this section we will discuss about conversion of Decimal to Binary in Java. You know that number having... be converted to binary and written as 1010. Example : Convert 12 into binary number

Java Beginners

Merge Sort String Array in Java
Merge Sort String Array in Java  Hello, I am trying to implement a merge sort algorithm that sorts an array of Strings. I have seen numerous.... Note: I have a separate class for merge sort in which i pass my list and the size

Java Tips and Examples

Selection Sort In Java
Selection Sort In Java      ... are going to sort the values of an array  using selection sort.In selection sorting.... Sort the remaining  values by using same steps. Selection sort

Java-Tutorials

Java Write To File Binary
Java Write To File Binary In this tutorial you will learn how to write to binary file. A binary file is a file into which the bit patterns of mostly data types can be formed to a byte of 8 bits. Write to a binary file in java

Java Tips and Examples

Merge Sort In Java
Merge Sort in Java      ... to sort integer values of an array using merge sort. In merge sorting.... Then merge both parts and sort it. Then again merge the next part and sort it. Do

Java Beginners

Java Binary data file - Java Beginners
Java Binary data file  Hi, I have a binary data file(binfile.data) and the file has what is commonly referred to as variable length... in the binary file.I have to do this using java.I tried to figure out the correct

Java Beginners

How to using Binary Search Array Java ?
How to using Binary Search Array Java ?  Hi, I am beginners in Java... functions. The problem is that how to use binary search array in Java. Please give any online reference show that i will implement the binary search array in Java

Java Tips and Examples

Quick Sort In Java
Quick Sort in Java      ...;java QuickSort RoseIndia Quick Sort... to sort integer values of an array using quick sort. Quick sort algorithm

Java Beginners

Help With Costructing Selection sort?
in advance!   Please visit the following link: Java Selection Sort...Help With Costructing Selection sort?  Using a selection sort, for each entry in the array, display the original index of the first dimension

Java Tips and Examples

How to sort ArrayList in java
How to sort ArrayList in java In this section you will learn how to sort ArrayList in java. ArrayList support dynamic array that can grow as needed. Array... which sort the Arraylist. Now here is the code to sort the ArrayList in java

Java Beginners

binary addition,subtraction and modulus operations - Java Beginners
adder binary logic in this!!! please send me the java coding for these three...binary addition,subtraction and modulus operations  i wanna perform binary addition,subtraction and modulus operation between two numbers of 512 bit

Java Tips and Examples

Selection Sort in Java
Selection sort in Java is used to sort the unsorted values in an array... in Java. In selection sort algorithm, first assign minimum index in key as index... the whole list is sorted. Example of Selection Sort in Java: public class

Java Technology Tutorials

Java File Binary
Java File Binary In this section, you will learn how to write numeric data into the binary file. Description of code: Numeric data converts compactly and faster in a binary format than the text. In the given example, at first, we have

Java Tips and Examples

Convert Number to Binary
Convert Number to Binary       In this section, you will learn to convert a number to a binary (0,1... binary. Code Description: This program takes a decimal number at the console

Java Tips and Examples

Convert Decimal into Binary
into binary. The java.lang package provides the functionality to convert  a decimal number into a binary number.  Description of program: This program takes a decimal number from console and it converts it  into binary format

Java Tips and Examples

Bidirectional Bubble Sort in Java
Bidirectional Bubble Sort in Java       Introduction : Bidirectional Bubble Sort In this example we are going to sort integer values

Java Tips and Examples

:\corejava>java BinaryToHexa Enter the Binary number: 1111111 Hexa... Convert Binary to Hexadecimal       In this section, you will learn to convert binary data

Java Beginners

Writing to and reading from a binary file in java.
Writing to and reading from a binary file in java.  I have written the following code to convert an ASCII text file to a binary file: public static... the binary file from another program as follows: m_dis = new DataInputStream

Java Beginners

Sort the element find mean
Sort the element find mean  Hi Friend, I want to find meaning of some real numbers like, if we have numbers- 52.15, 89.0, 314.48, 845.75... developing this program in java..Please help me to solve this problem ASAP

Java-Tutorials

Bubble Sort in Java
Bubble Sort aka exchange sort in Java is used to sort integer values... of Bubble Sort in Java: public class BubbleSort { public static void main(String... Sort compares first pair of adjacent elements and put larger value at higher

General

Iterator Java Sort
Sort is a static method of the Collections class. It sorts the contents of the list Collection. Example of Java Sort Iterator import... java.util.Iterator; import java.util.List; public class sort { public