Binary search
It's an algorithm which is optimized way to find a element in array.
let's take an example array which is sorted.
arr[] = {1,2,3,4,5,6};
Here target is to find 5.
first it will take no of index here 5 after it will take half of the index = 2 the element in 2 index is 3. 3 is lesser then 5 again from index 3 to 5 it will take the half. If the element 4 is greater than target it will search from index 0 to 2. Now index is 4 and element is 5. and 5 is equal to target and it prints the output.
Example
arr[] = {1,5,7,9,10,15}; target = 10;
1st - index = 5
Start = 0 end= 5
binary search = 0+5/2 -> 2(index)
Value in index 2 is 7 and 7 is lesser than target.
2nd - {9,10,15}
Start = 3 end = 5
binary = 3+5/2 -> 4(index)
Value in index 4 is 10 and its equal to target.
Now output is index 4.
Time complexity -
Best case - O(1) //size does not matter if element is found in first index
Worst Case - logN.
public class BinarySearch {
public static void main(String[] args) {
int arr[] = {1,2,3,5,6,7,9,10};
int target = 6;
int ans =binarySearch(arr,target);
System.out.println(ans);
}
static int binarySearch(int[] arr, int target) {
int start =0;
int end = arr.length-1;
while(start <= end) {
int mid = start+(end-start)/2;
if(target < arr[mid]) {
end = mid-1;
}else if(target > arr[mid]) {
start = mid+1;
}else {
return mid;
}
}
return -1;
}
}
Output - 4
Top comments (0)