### Linear Search – O(n)

Go through the entire array and check if the element exists

```static int LinearSearch(int arr[], int x) {
int n = arr.length;
for (int i = 0; i < n; i++) {
if (arr[i] == x) {
return i;
}
}
} ```

### Binary Search – O(n log(n))

• Compare x with the middle element.
• If x matches with middle element, we return the mid index.
• If x is greater than the mid element, then do a Binary Search for right half.
• If x is left is lower, then do a Binary Search for left half.
```//Recursive
int binarySearch(int arr[], int left, int right, int x) {
if (right>=left) {
int mid = left + (right - left)/2;
if (arr[mid] == x) {
return mid;
}
if (arr[mid] > x) {
return binarySearch(arr, left, mid-1, x);
} else {
return binarySearch(arr, mid+1, right, x);
}
}
return -1;
}

//Non Recursive
int binarySearch(int arr[], int x) {
int left = 0, right= arr.length - 1;
while (left<= r) {
int mid = left + (right - left)/2;
if (arr[mid] == x) {
return mid;
}
if (arr[mid] < x) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}

// Array =[2, 3, 4, 10, 40, 50, 60, 70, 80, 90]
// Mid = 4 Left = 0 Right = 9
// Mid = 7 Left = 5 Right = 9
// Mid = 8 Left = 8 Right = 9
// Element found at index 8```

### ExponentialSearch – O(log(n))

• Find the range where element is present
• Do Binary Search in above found range.
```static int exponentialSearch(int arr[], int n, int x) {
if (arr == x)
return 0;
// Find range for binary search by
// repeated doubling
int i = 1;
for (;i < n && arr[i]<=x;i=i*2);
// Call binary search for the found range.
return Arrays.binarySearch(arr,i/2,Math.min(i, n), x);
// binarySearch(Array,fromIndex,toIndex,keyToFind)
} ```

### JumpSearch – √(n)

• Loop, jump and add the step to i
• linearly traverse the array till the array element is less the required element
• and the previous element index is less than i
```public static int jump_search(int[] arr, int x) {
int n = arr.length;
int step = (int) Math.floor(Math.sqrt(n));
int prev = 0, i = 0;

for (; i < n && arr[i] < x; prev = i, i += step);

if (i >= n) return -1;

for (++prev; arr[prev] < x && prev < i; ++prev);

return (arr[prev] == x) ? prev : -1;
} ```

### InterpolationSearch – O(n)

• The Interpolation Search is an improvement over Binary Search
• interpolation search may go to different locations according to the value of the key being searched
• if the value of the key is closer to the last element, interpolation search is likely to start search toward the end side.
```static int interpolationSearch1(int arr[],int x) {
int low = 0, high = (arr.length - 1),pos;

for (;low <= high && x >= arr[low] && x <= arr[high];) {
pos = low + (((high-low) / (arr[high]-arr[low]))*(x - arr[low]));

if (arr[pos]==x) {
return pos;
}else if (arr[pos]<x) {
low=pos+1;
}else {
high=low-1;
}
}
return -1;
}```