# Khan Academy - Computing

## Unit_1. Algorithmns
Computing
Computer science theory

**About this unit**
We've partnered with Dartmouth college professors Tom Cormen and Devin Balkcom to teach introductory computer science algorithms, including searching, sorting, recursion, and graph theory. Learn with a combination of articles, visualizations, quizzes, and coding challenges.

**Intro to algorithms**
What are algorithms and why should you care? We'll start with an overview of algorithms and then discuss two games that you could use an algorithm to solve more efficiently - the number guessing game and a route-finding game.

**Binary search**
Binary search is an efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing in half the portion of the list that could contain the item, until you've narrowed down the possible locations to just one.

**Pseudocode**
Here's the pseudocode for binary search, modified for searching in an array. The inputs are the array, which we call array; the number n of elements in array; and target, the number being searched for. The output is the index in array of target:

1. Let min = 0 and max = n-1.
Compute guess as the average of max and min, rounded down (so that it is an integer).
2. If array[guess] equals target, then stop. You found it! Return guess.
3. If the guess was too low, that is, array[guess] < target, then set min = guess + 1.
4. Otherwise, the guess was too high. Set max = guess - 1.
5. Go back to step 2.

The parameters to the function—let's call it **binarySearch**— will be the array and target value, and the return value of the function will be the index of the location where the target value was found.

Here is *modified pseudocode for binary search that handles the case in which the target number is **not present:***

1. Let min = 0 and max = n-1.
2. If max < min, then stop: target is not present in array. Return -1.
3. Compute guess as the average of max and min, rounded down (so that it is an integer).
4. If array[guess] equals target, then stop. You found it! Return guess.
5. If the guess was too low, that is, array[guess] < target, then set min = guess + 1.
6. Otherwise, the guess was too high. Set max = guess - 1.
7. Go back to step 2.

**Python Code**

def binary_search(array, n, target):
    min_index = 0
    max_index = n - 1

    while min_index <= max_index:
        guess = (min_index + max_index) // 2

        if array[guess] == target:
            return guess  # Target found at index guess
        elif array[guess] < target:
            min_index = guess + 1
        else:
            max_index = guess - 1

    return -1  # Target not found in the array

# Example usage
arr = [2, 5, 7, 12, 18, 24, 35, 47]
num_elements = len(arr)
search_target = 18

result_index = binary_search(arr, num_elements, search_target)

if result_index != -1:
    print(f"Target {search_target} found at index {result_index}.")
else:
    print(f"Target {search_target} not found in the array.")

This Python code defines a binary_search function that performs a binary search on a sorted array to find a target element. The function takes the array, the number of elements in the array, and the target value as inputs. It returns the index of the target element if found or -1 if the target is not present in the array. The example usage demonstrates how to use the binary_search function to search for the number 18 in the provided sorted array and prints the result accordingly.