In this tutorial we will come across 'Search Algorithms in Java ' and their Implementation. Linear Search and Binary Search are two commonly used Search Algorithms used in Java Programming. In this particular blog we will come across their implementation and difference in details.

In this particular blog we came across 'Linear and Binary Search in Java' and their Implementation. In upcoming blogs we will come across more about Java and other open source Technologies.

Thanks for reading !

**Linear Search is the most easiest way of searching elements from an Array or Collection. In this approach we iterate over an Array or collection and try every element in the collection until we have found the element or until we reach the end of the collection or Array. Here is a simple Java Program to demonstrate working of Linear Search.**## Linear Search Implementation in Java

package com.beingjavaguys.core; /** * * @author Nagesh Chauhan */ public class LinearSearch { int searchElementLinear(int numList[], int toSearch) { int foundIndex = 0; for (int i = 0; i < numList.length; i++) { if (numList[i] == toSearch) { foundIndex = i; } } return foundIndex; } }

**Linear Search iterate over each element until it found the right element hence it has a variable best case and a fixed average and worst case complexity of 'O(n)'.**## Linear Search Complexity in Java

**Binary search is more efficient and merely used search algorithm in java programming. To implement Binary search we must have an sorted array or collection. Binary Search searches element in middle of the Array. The array is than divided into sub-array in each iteration accordingly, if the element is greater than the middle element or smaller than the middle element the respective sub-array is used for further searching. Here is a simple Java Program demonstrating binary search in Java.**## Binary Search Implementation in Java

package com.beingjavaguys.core; /** * * @author Nagesh Chauhan */ public class BinarySearch { int searchElementBinary(int numList[], int toSearch) { int startIndex = 0; int endIndex = numList.length - 1; int midindex = (startIndex + endIndex) / 2; int midElement = numList[midindex]; int foundIndex = 0; while (startIndex <= endIndex) { if (midElement < toSearch) { startIndex = midindex + 1; midindex = (startIndex + endIndex) / 2; midElement = numList[midindex]; } else if (midElement > toSearch) { endIndex = midindex - 1; midindex = (startIndex + endIndex) / 2; midElement = numList[midindex]; } else { foundIndex = midindex; break; } } return foundIndex; } }

**Binary Search divided the search space into half in each iteration and hence has a 'O(log n)' complexity.**## Binary Search Complexity in Java

**This is a simple java class to demonstrate the actual implementation.**## Implementation Class Code

package com.beingjavaguys.core; /** * * @author Nagesh Chauhan */ public class Implementation { public static void main(String args[]) { int numList[] = { 1, 3, 8, 12, 34, 56, 78, 87, 92 }; int toSearch = 12; LinearSearch linearSearch = new LinearSearch(); BinarySearch binarySearch = new BinarySearch(); System.out.println("Linear Search Index : " + linearSearch.searchElementLinear(numList, toSearch)); System.out.println("Binary Search Index : " + binarySearch.searchElementBinary(numList, toSearch)); } }

In this particular blog we came across 'Linear and Binary Search in Java' and their Implementation. In upcoming blogs we will come across more about Java and other open source Technologies.

Thanks for reading !

**Being Java Guys Team**

The implementation of Binary Search contains a potential bug. The bug is in the calculation of mid using:

ReplyDeleteint midindex = (startIndex + endIndex) / 2;

This line effectively says "sets midindex to the average of endIndexand u, truncated down to the nearest integer.". This assertion might appear correct, but it fails for large values of the int variables startIndex and endIndex. Specifically, it fails if the sum of startIndex and endIndex is greater than the maximum positive int value (231 - 1). The sum overflows to a negative value, and the value stays negative when divided by two. In C this causes an array index out of bounds with unpredictable results. In Java, it throws ArrayIndexOutOfBoundsException. So what's the best way to fix the bug?

Here is one way:

int midindex = startIndex + ((endIndex- startIndex ) / 2);

or more faster:

int midindex = (startIndex + endIndex) >>> 1;

Cheers.

Simple and good article

ReplyDelete