Linear Search
• The linear search algorithm is defined as a sequential search
algorithm that starts at one end and goes through each
element of a list until the desired element is found;
otherwise, the search continues till the end of the dataset.
Linear Search
class Linear {
public static int search(int arr[], int N, int x)
{
for (int i = 0; i < N; i++) {
if (arr[i] == x)
return i;
}
return -1;
}
public static void main(String args[])
{
int arr[] = { 2, 7,3, 4, 30,10, 40,20,9 };
int x = 4;
int result = search(arr, arr.length, x);
if (result == -1)
System.out.print("Element is not present in array");
else
System.out.print("Element is present at index " + result);
}}
Binary Search
Binary search is a search algorithm used to find the position of a
target value within a sorted array. It works by repeatedly dividing
the search interval in half until the target value is found or the
interval is empty. The search interval is halved by comparing the
target element with the middle value of the search space.
mid = low + (high - low) / 2
Binary Search
class BinarySearch { public static void main(String args[])
static int binarySearch(int arr[], int x) {
{ int arr[] = { 2, 3, 4, 10, 40 };
int n = arr.length;
int low = 0, high = arr.length - 1; int x = 40;
while (low <= high) { int result = binarySearch(arr, x);
int mid = low + (high - low) / 2;
if (arr[mid] == x) if (result == -1)
System.out.println("Element is
return mid; not present in array");
if (arr[mid] < x)
low = mid + 1; else
else System.out.println("Element is
high = mid - 1; present at " + "index " + result);
}
} }
return -1;
}
Binary Search (using Recursion)
class BinarySearch {
public static void main(String args[])
static int binarySearch(int arr[], int low,
{
int high, int x)
int arr[] = { 2, 3, 4, 10, 30, 35, 40, 50 };
{ if (high < low) int n = arr.length;
return -1; int x =35;
int result = binarySearch(arr, 0, n - 1, x);
int mid = low + (high - low) / 2;
if (result == -1)
if (arr[mid] == x)
System.out.println("Element is not
return mid; present in array");
if (arr[mid] > x)
return binarySearch(arr, low, mid - 1, x); else
System.out.println("Element is present
at index " + result);
return binarySearch(arr, mid + 1, high, x);
}
} }
Time Complexity: O(log N)
Exercise:
Show all the steps while searching for 10, 30, 50, 80 and 90 in
the following array elements in case of binary search.
10, 20, 30, 35, 45, 50, 60, 70, 75, 80
