Search Algorithm using JAVA — 2
In this article we will get to know about Binary Search.
2. Binary Search :
Binary search also known as half-interval search, logarithmic search or binary chop, is a search algorithm that finds the position of a target value within a sorted array.
- Array must be sorted first to apply Binary Search.
- Binary search cut down your search to half as soon as you find middle of a sorted list.
- The middle element is looked to check if it is greater than or less than the value to be searched.
- Search is done to either half of the given list.
- Binary search has time complexity O(log n) — where n is the number of element in the array.
- Binary search is faster than Linear search except for small arrays.
Binary Search Example Code :
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.println(“Enter the array size”);
int arr_size = scanner.nextInt();
int[] arr = new int[arr_size];
for (int i = 0; i < arr.length; i++){
arr[i] = scanner.nextInt();
}
System.out.println(“Enter search element”);
int search_element = scanner.nextInt();
int result = binarySearch(arr, 0, arr.length — 1, search_element);
if (result == -1)
System.out.println(“Element not present”);
else
System.out.println(“Element index is = “+result);
scanner.close();
}
private static int binarySearch(int[] arr, int l, int r, int x ){
// l = initial postion 0, and r = length of the array, x = search element //
if (r >= l){
int mid = l + (r — l)/2 ;
if (arr[mid] == x)
return mid;
if (arr[mid] > x)
return binarySearch(arr, l , mid -1, x);
return binarySearch(arr, mid + 1, r, x); } return -1;
}
GitHub link for Binary search code.
Follow me on GitHub for more data structure and algorithm practice.
In the next article we will get to know about Jump Search.