Searching
15pts
Python
Java
C++
Algorithms
Data
What is searching, what is binary search, and why is it useful
Searching is an important operation used to find an element in a set of data. For example, every time a user completes an article on this website, we need to search our databases for the user to add points to their account. The most common form of this task is: Given an array of integers, what is the index of a given target element? For example, if we are given [1, 3, 5, 2, 4] and our target element is 5 we want to get its index, 2.
The simplest method to achieve this is linear search. Linear search works by iterating straight through an array and returning the index of the target element as soon as it finds it. Here’s what it would look like:
Code: 
def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
            
arr = [1, 3, 5, 2, 4]
print(linear_search(arr, 5))
print(linear_search(arr, 1))
print(linear_search(arr, 4))
Output:
> 2
> 0
> 4
Code: 
class linearSearch {
    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 2, 4};
        System.out.println(linear_search(arr, 5));
        System.out.println(linear_search(arr, 1));
        System.out.println(linear_search(arr, 4));
    }
    static int linear_search(int[] arr, int target) {
        for(int i = 0; i < arr.length; i++) {
            if(arr[i] == target) {
                return i;
            }
        }
        return -1;
    }
}
Output:
> 2
> 0
> 4
Code: 
#include <bits/stdc++.h>

using namespace std;

int linear_search(int arr[], int target) {
    for(int i = 0; i < 5; i++) {
        if(arr[i] == target) {
            return i;
        }
    }
    return -1;
}

int main() {
    int arr[] = {1, 3, 5, 2, 4};
    cout << linear_search(arr, 5) << "\n";
    cout << linear_search(arr, 1) << "\n";
    cout << linear_search(arr, 4);
    return 0;
}
Output:
> 2
> 0
> 4
In some cases, linear search is about as efficient as searching gets (e.g., in an array of random numbers). However, when your array is sorted, binary search is much faster.
Do you remember the last time you needed to find a word in a dictionary? If so, do you remember your strategy? If you simply flipped from left to right, it would take ages — especially if your word started with Z! However, if you started in the middle of the book, then flipped left or right depending on if the word you were looking for came after that page, repeating until you found the right word, you were emulating binary search, one of the most common, essential techniques in computer science.
Binary search is a super-efficient algorithm that finds a target element in sorted data (imagine how difficult it would be to find a word if your dictionary had words in random order!). Once your data is sorted, the algorithm works by continuously halving the possible locations of your element until you find it.
Binary search does this using a search window, or the window the algorithm is certain the target element is located in. This window is defined by a left and right index. Every iteration, the algorithm finds the center of the window (by averaging the left and right indices), compares the center to the target element, and figures out in which half of the window the target element is located. Then, it redefines the window to that half. Searching an integer array using binary search is implemented like this:
Code: 
def binary_search(arr, target):
    left = 0
    right = len(arr) - 1
    mid = (left + right) // 2 # this method of calculating mid is the most straightforward, but breaks in certain cases- google the better method!
    
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] > target:
            right = mid - 1
        else:
            left = mid + 1
            
    return -1
            
arr = [1, 4, 8, 9, 26]
print(binary_search(arr, 4))
print(binary_search(arr, 9))
print(binary_search(arr, 26))
Output:
> 1
> 3
> 4
Code: 
class binarySearch {
    public static void main(String[] args) {
        int[] arr = {1, 4, 8, 9, 26};
        System.out.println(binary_search(arr, 4));
        System.out.println(binary_search(arr, 9));
        System.out.println(binary_search(arr, 26));
    }
    static int binary_search(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        int mid = (left + right) / 2; // this method of calculating mid is the most straightforward, but breaks in certain cases- google the better method!
        
        while(left <= right) {
            mid = (left + right) / 2;
            if(arr[mid] == target) {
                return mid;
            } else if(arr[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }
}
Output:
> 1
> 3
> 4
Code: 
#include <bits/stdc++.h>

using namespace std;

int binary_search(int arr[], int target) {
    int left = 0;
    int right = 4;
    int mid = (left + right) / 2; // this method of calculating mid is the most straightforward, but breaks in certain cases- google the better method!
    
    while(left <= right) {
        mid = (left + right) / 2;
        if(arr[mid] == target) {
            return mid;
        } else if(arr[mid] > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return -1;
}

int main() {
    int arr[] = {1, 4, 8, 9, 26};
    cout << binary_search(arr, 4) << "\n";
    cout << binary_search(arr, 9) << "\n";
    cout << binary_search(arr, 26);
    return 0;
}
Output:
> 1
> 3
> 4
Common Mistake: Make sure your data is sorted!
Binary search is much faster than linear search. If the target element is the last element in the data, linear search will have a worst-case scenario of going through every single element before finding the correct one. This would take
N
operations to complete, where
N
is the size of the array. With binary search, the search window is cut in half every time the algorithm executes. This results in a much faster maximum of
log2(N)
operations.
However, that’s the maximum number of operations, not the actual number of operations. It’s important to know what data you are working with. For example, if your target element is always going to be the first element, linear search will always run faster than binary search on large arrays (1 operation is faster than
log2(N)
operations!). Know your data!
Binary search has a slew of useful applications in the real world. The most obvious is searching for a specific value (no kidding), but it is also applied in several more complicated algorithms as well. Its ability to cut down the time it takes to find a value helps dramatically in speeding up a program.
Two Pointers
Two pointers is a technique commonly used to search for pairs in a sorted array. The idea is to create two markers (pointers) to keep track of your position in the array. The pointers are then iterated across an array to search for a pair of indices that satisfy some condition in linear time.
In this article, we will go over the textbook example of a two-pointers problem: finding two array elements that sum up to a certain number.
Naively, the problem can be solved by using two for loops, checking each pair of elements. However, this solution runs in O(n2) time, which may exceed the time limit for test cases with larger inputs. A more efficient method to solve this problem would be to use two-pointers.
With two pointers, the first pointer starts at the beginning of the array, and the second pointer starts at the end of the array. Using a while loop, the sum of the first and second pointers is compared to the desired sum. If the sum is larger than desired, the second pointer is moved down one element; notice that because the array is sorted from least to greatest, moving the right pointer to the left by one element decreases the overall sum. If the sum is smaller than desired, using similar logic as before, the first pointer is moved up one element.
Note that this method can only be used on a sorted array. Therefore, the time complexity of this solution would be O(n log n) if the array has not yet been sorted, and O(n) if it has been sorted; both are more efficient than the naive O(n2) solution.
An implementation of the said algorithm can be found below.
the implementation below uses a single while loop, but there are other implementations that include for loops or a combination of for loops and while loops.
Code: 
arr = [1, 3, 6, 8, 10]
def two_pointers(arr, sum):
  first = 0
  second = len(arr)-1
  while first<second:
    if arr[first]+arr[second]>sum:
      second=second-1
    elif arr[first]+arr[second]<sum:
      first=first+1
    else:
      print(first, second)
      return

two_pointers(arr, 14)
Output:
2, 3
Code: 
public class Main {
  static int[] arr = {1, 3, 6, 8, 10};

  public static void two_pointers (int[] arr, int sum) {
    int first = 0;
    int second = arr.length-1;
    while (first<second) {
      if (arr[first]+arr[second]>sum) {
        second--;
      }
      else if (arr[first]+arr[second]<sum) {
        first++;
      }
      else {
        System.out.println(first + " " + second);
        return;
      }
      }
  }

   public static void main(String[] args) {
      two_pointers(arr, 14);
  }
}
Output:
2, 3
Code: 
#include <bits/stdc++.h>
using namespace std;

vector<int> arr = {1, 3, 6, 8, 10};

void two_pointers (vector<int> arr, int sum) { 
  int first = 0;
  int second = arr.size()-1;
  while (first<second) {
    if (arr[first]+arr[second]>sum) {
      second--;
    }
    else if (arr[first]+arr[second]<sum) {
      first++;
    }
    else {
      cout << first << " " << second << endl;
      return;
    }
  }
}

int main() {
  two_pointers(arr, 14);
}
Output:
2, 3
You can play around with all the code we've used in this article on Replit:
Copyright ©2023 Howard County Hour of Code