Binary Search Algorithm: Search a Sorted Array

105.4k
0

Given a sorted array arr[] and an integer X, return the index of X if it is present in the array.

If X is not present, return -1.

Example 1

Input: arr = [1, 3, 5, 7, 9, 11], x = 7

Output: 3

Explanation: The target value 7 is present at index 3 of the array.

Example 2

Input: arr = [1, 3, 5, 7, 9, 11], x = 4

Output: -1

Explanation: The target value 4 is not present anywhere in the array, so we return -1.

Brute Force Approach

The most straightforward method is to start at the very beginning and look at each item one by one. You check the first item, then the second, then the third, moving sequentially until you either find the target or reach the end of the list.

Algorithm

  • Start a loop from index 0 up to n - 1, where n is the size of the array, this is done to check values at all valid index.

  • At each index i, check if arr[i] is equal to the given target x.

  • If a match is found, immediately return the current index i.

  • If the loop finishes without finding x, return -1 because X is not found in the arr.

Dry Run

Search X in a Sorted Array Brute Dry Run

Search X in a Sorted Array Brute Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Function to search for x using linear search
int linearSearch(vector<int>& arr, int x) {
int n = arr.size();
// Loop through every element of the array sequentially
for (int i = 0; i < n; i++) {
// Check if the current element matches the target
if (arr[i] == x) {
// Return the index where the match is found
return i;
}
}
// Return -1 if the target is not found in the array
return -1;
}
};
// Driver code to test the linear search implementation
int main() {
Solution solver;
vector<int> arr = {1, 3, 5, 7, 9, 11};
int x = 7;
int result = solver.linearSearch(arr, x);
cout << "Index of " << x << ": " << result << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N), where N is size of array. because in the worst-case scenario, the target element might be at the very end of the array or not present at all, requiring us to check all n elements.

Space Complexity: O(1), as the algorithm only uses a few variables for iteration and does not require any additional memory allocation that scales with the input size.

Optimal Approach

The sorted order gives the main clue.

If the middle element is smaller than X, then everything on the left side is also smaller than X. That entire half becomes useless for the search.

If the middle element is greater than X, then everything on the right side is also greater than X. That half can also be ignored.

So instead of checking every element one by one, the search space keeps getting cut into half. That is why binary search becomes much faster than linear search on a sorted array.

Algorithm

  • Start with two pointers, low at the first index and high at the last index, because the search can begin anywhere inside the full array.

  • Find the middle index using mid = low + (high - low) / 2 because low + high can exceed the int limit for larger arrays. (integer division is used).

  • If arr[mid] == X, return mid because the target has been found.

  • If arr[mid] < X, move low to mid + 1 because the left half cannot contain X anymore.

  • Otherwise, move high to mid - 1 because the right half cannot contain X.

  • Keep repeating this while low <= high, because that means a valid search range still exists if low > high it means search space is covered.

  • If the loop finishes, return -1 because the target was not found in any valid position.

Dry Run

Search X Optimal Dry Run

Search X Optimal Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
/*
Returns the index of x in the sorted array,
or returns -1 if x is not present.
*/
int searchInSortedArray(vector<int>& arr, int x) {
// Left boundary of the current search range.
int low = 0;
// Right boundary of the current search range.
int high = (int)arr.size() - 1;
// Keep searching while a valid range still exists.
while (low <= high) {
// Calculate the middle index safely.
int mid = low + (high - low) / 2;
// If the middle value matches x, the answer is found.
if (arr[mid] == x) {
return mid;
}
// If x is larger, search only in the right half.
if (arr[mid] < x) {
low = mid + 1;
} else {
// If x is smaller, search only in the left half.
high = mid - 1;
}
}
return -1;
}
};
// Driver code starts
int main() {
vector<int> arr = {2, 4, 7, 10, 14, 19};
int x = 10;
Solution obj;
cout << obj.searchInSortedArray(arr, x) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(log2 N), where N is length of array, because the search range becomes half after every step.

Space Complexity: O(1), because only a few index variables are used.

Interview follow-up Questions

This basic version can return any index where X is present. If the problem asks for the first or last occurrence, a modified binary search is needed.

Two PointerSortingMathsBinary SearchGreedy

Read Similar Blogs

MathsIntroduction to DSA

Mastering Number Basics in Programming

Introduction Numbers are one of the first things that appear in DSA, and they are much friendlier than they look. A number can be checked, divided, broken into digits, counted, and compared. These...

73.6k
MathsGreedyIntroduction to DSA

Find Remainder

Given two non-negative integers a and b , find the remainder when a is divided by b . Assume b is not 0 . Approach The small observation is very direct: the remainder is exactly what the modulo ope...

95.9k
Introduction to DSABit ManipulationMaths

Check Even or Odd

Given an integer N , determine whether it is even or odd. Return "Even" if the number is divisible by 2 , otherwise return "Odd" . Approach The first observation is the whole key: even and odd numb...

68.5k
Comments0