Discussions
Categories
- 196.9K All Categories
- 2.2K Data
- 239 Big Data Appliance
- 1.9K Data Science
- 450.3K Databases
- 221.7K General Database Discussions
- 3.8K Java and JavaScript in the Database
- 31 Multilingual Engine
- 550 MySQL Community Space
- 478 NoSQL Database
- 7.9K Oracle Database Express Edition (XE)
- 3K ORDS, SODA & JSON in the Database
- 545 SQLcl
- 4K SQL Developer Data Modeler
- 187K SQL & PL/SQL
- 21.3K SQL Developer
- 295.9K Development
- 17 Developer Projects
- 138 Programming Languages
- 292.6K Development Tools
- 107 DevOps
- 3.1K QA/Testing
- 646K Java
- 28 Java Learning Subscription
- 37K Database Connectivity
- 155 Java Community Process
- 105 Java 25
- 22.1K Java APIs
- 138.1K Java Development Tools
- 165.3K Java EE (Java Enterprise Edition)
- 18 Java Essentials
- 160 Java 8 Questions
- 86K Java Programming
- 80 Java Puzzle Ball
- 65.1K New To Java
- 1.7K Training / Learning / Certification
- 13.8K Java HotSpot Virtual Machine
- 94.3K Java SE
- 13.8K Java Security
- 204 Java User Groups
- 24 JavaScript - Nashorn
- Programs
- 440 LiveLabs
- 38 Workshops
- 10.2K Software
- 6.7K Berkeley DB Family
- 3.5K JHeadstart
- 5.7K Other Languages
- 2.3K Chinese
- 171 Deutsche Oracle Community
- 1.1K Español
- 1.9K Japanese
- 232 Portuguese
Binary Search: Searching last & first Element

Hi,
I have coded Binary Search in java but its returning -1 when i am trying to search last or first element. If first works then last doesnt work & if last works first doesnt work. My code is given below:
import javax.swing.*;
public class BinarySearch{
int[ ] Array = new int[10];
BinarySearch(int[ ] a ) {
Array = a;
}
int BinarySearchAlg(int num, int first, int last ) {
int index=-1;
if(first < last) {
int mid = first + ((last - first) / 2);
//int mid = (first + last)/2;
JOptionPane.showMessageDialog(null, "mid= " + mid);
if(num == Array[mid])
index = mid;
else if(num < Array[mid])
index = BinarySearchAlg(num, first, mid-1);
else
index = BinarySearchAlg(num, mid+1, last);
}
return index;
}
public static void main(String[ ] args) {
int[ ] a = {1, 12, 19, 56, 100, 134, 145, 178, 199, 201};
BinarySearch obj = new BinarySearch(a);
int index=obj.BinarySearchAlg(1, 1, 10);
//int index=obj.BinarySearchAlg(201, 0, 9);
JOptionPane.showMessageDialog(null, "index= " + index);
}
}
When i tried the following statement:
int index=obj.BinarySearchAlg(1, 1, 10);
it returns -1 (i.e it cant search 1 in the array
& when i tried:
int index=obj.BinarySearchAlg(201, 0, 9);
it returns -1(i.e. it cant search 201 in the array.
Somebody please guide me.
Zulfi.
Best Answer
-
Hi,
Thanks everybody. I am able to correct my program:
import javax.swing.*;
public class BinarySearch{
int[ ] Array = new int[10];
BinarySearch(int[ ] a ) {
Array = a;
}
int BinarySearchAlg(int num, int first, int last ) {
int index=-1;
if(first <= last) {
//int mid = first + ((last - first) / 2);
int mid = (first + last)/2;
JOptionPane.showMessageDialog(null, "mid= " + mid + "first ="+ first + "last=" + last);
if(num == Array[mid])
index = mid;
else if(num < Array[mid])
index = BinarySearchAlg(num, first, mid-1);
else{
index = BinarySearchAlg(num, mid+1, last);
}
}
return index;
}
public static void main(String[ ] args) {
int[ ] a = {1, 12, 19, 56, 100, 134, 145, 178, 199, 201};
BinarySearch obj = new BinarySearch(a);
int index=obj.BinarySearchAlg(199, 0, 10);
//int index=obj.BinarySearchAlg(201, 0, 9);
JOptionPane.showMessageDialog(null, "index= " + index);
}
}
Correction is highlighted.
Zulfi.
Answers
-
what does "it does not work" mean in particular?
bye
TPD
-
Hi,
<
what does "it does not work" mean in particular?>
It means that its not able to search the first & last element.
Zulfi.
-
If first = last then -1 is returned without checking the value.
Why don't you trace your program? You'd see it yourself.
-
Hi,
Thanks everybody. I am able to correct my program:
import javax.swing.*;
public class BinarySearch{
int[ ] Array = new int[10];
BinarySearch(int[ ] a ) {
Array = a;
}
int BinarySearchAlg(int num, int first, int last ) {
int index=-1;
if(first <= last) {
//int mid = first + ((last - first) / 2);
int mid = (first + last)/2;
JOptionPane.showMessageDialog(null, "mid= " + mid + "first ="+ first + "last=" + last);
if(num == Array[mid])
index = mid;
else if(num < Array[mid])
index = BinarySearchAlg(num, first, mid-1);
else{
index = BinarySearchAlg(num, mid+1, last);
}
}
return index;
}
public static void main(String[ ] args) {
int[ ] a = {1, 12, 19, 56, 100, 134, 145, 178, 199, 201};
BinarySearch obj = new BinarySearch(a);
int index=obj.BinarySearchAlg(199, 0, 10);
//int index=obj.BinarySearchAlg(201, 0, 9);
JOptionPane.showMessageDialog(null, "index= " + index);
}
}
Correction is highlighted.
Zulfi.
-
The fact that a program produces correct results does not mean it is a correct answer - binary search is not an algorithm that needs to be recursive (and as such it should not be):
int BinarySearchAlg(int num, int first, int last ) {
while (true) {
if (first > last) {
return -1;
}
if (first == last)
if (Array[first] == num) {
return first;
} else {
return -1;
}
int mid = first + ((last - first) / 2);
if(num == Array[mid]) {
return mid;
}
if (num < Array[mid]) {
last = mid -1;
} else {
first = mid + 1;
}
}
}
-
Hi,
Thanks for referring Iterative version of Binary Search. Sorry your if construct is confusing. I got the following:
public class BinarySearchIterative{
int[ ] Array = new int[10];
BinarySearchIterative(int[ ] a ) {
Array = a;
}
int BinarySearchAlg(int num, int first, int last ) {
int index=-1;
while(first <= last) {
int mid= (first + last)/2;
if(num < Array[mid])
last = mid -1;
else if(num > Array[mid])
first = mid + 1;
else
return mid;
}
return index;
}
public static void main(String[ ] args) {
int[ ] a = {1, 12, 19, 56, 100, 134, 145, 178, 199, 201};
BinarySearchIterative obj = new BinarySearchIterative(a);
int index=obj.BinarySearchAlg(201, 0, 10);
//int index=obj.BinarySearchAlg(201, 0, 9);
JOptionPane.showMessageDialog(null, "index= " + index);
}
}
Any way i appreciate your quick response. Indeed you are a great helper.
Zulfi.