Search String in Sorted String Array Using Binary search

Binary Search: Search a sorted array by repeatedly dividing the search interval in half. Begin with an interval covering the whole array. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise narrow it to the upper half. Repeatedly check until the value is found or the interval is empty.

We basically ignore half of the elements just after one comparison.

1. Compare x with the middle element
2. If x matches with middle element, we return the mid index.
3. Else If x is greater than the mid element, then x can only lie in right half subarray after the mid element. So we recur for right half.
4. Else (x is smaller) recur for the left half.

Here I will show you an example which find string in array of sorted string:-

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

public class BinarySearchInStringArray { public static void main(String ar[]){ String str [] = {"account","angel","apple","application","black"}; String searchString = "application"; int length = str.length-1; BinarySearchInStringArray findStrin = new BinarySearchInStringArray(); int i = findStrin.find(str, 0, length, searchString); System.out.println(i); } public int find(String first[], int start, int end, String searchString){ int mid = start + (end-start)/2; // start = 0; if(first[mid].compareTo(searchString)==0){ return mid; } if(first[mid].compareTo(searchString)> 0){ return find(first, start, mid-1, searchString); }else if(first[mid].compareTo(searchString)< 0){ return find(first, mid+1, end, searchString); } return -1; } }

Output:Index value is: 3