Magic Index

Introduction

In computer science, a magic index (also known as a fixed point) of an array is an index i in the array such that its value is equal to i. In other words, the task is to find an element in the array such that its value is equal to its index.

Skills Graph

%%%%{init: {'theme':'neutral'}}%%%% flowchart RL algorithm(("`Algorithm`")) -.-> algorithm/BasicAlgorithmsGroup(["`Basic Algorithms`"]) python(("`Python`")) -.-> python/ControlFlowGroup(["`Control Flow`"]) python(("`Python`")) -.-> python/DataStructuresGroup(["`Data Structures`"]) python(("`Python`")) -.-> python/FunctionsGroup(["`Functions`"]) python(("`Python`")) -.-> python/ObjectOrientedProgrammingGroup(["`Object-Oriented Programming`"]) algorithm/BasicAlgorithmsGroup -.-> algorithm/recursion_dynamic("`Recursion Dynamic`") python/ControlFlowGroup -.-> python/conditional_statements("`Conditional Statements`") python/DataStructuresGroup -.-> python/lists("`Lists`") python/DataStructuresGroup -.-> python/tuples("`Tuples`") python/FunctionsGroup -.-> python/function_definition("`Function Definition`") python/ObjectOrientedProgrammingGroup -.-> python/classes_objects("`Classes and Objects`") python/ObjectOrientedProgrammingGroup -.-> python/encapsulation("`Encapsulation`") python/FunctionsGroup -.-> python/build_in_functions("`Build-in Functions`") subgraph Lab Skills algorithm/recursion_dynamic -.-> lab-268866{{"`Identifying Magic Indexes in Arrays`"}} python/conditional_statements -.-> lab-268866{{"`Identifying Magic Indexes in Arrays`"}} python/lists -.-> lab-268866{{"`Identifying Magic Indexes in Arrays`"}} python/tuples -.-> lab-268866{{"`Identifying Magic Indexes in Arrays`"}} python/function_definition -.-> lab-268866{{"`Identifying Magic Indexes in Arrays`"}} python/classes_objects -.-> lab-268866{{"`Identifying Magic Indexes in Arrays`"}} python/encapsulation -.-> lab-268866{{"`Identifying Magic Indexes in Arrays`"}} python/build_in_functions -.-> lab-268866{{"`Identifying Magic Indexes in Arrays`"}} end

Problem

Given a sorted array of integers with possible duplicates, write a Python function to find the magic index, if one exists, in the array. If there are multiple magic values, return the left-most one. If there is no magic index, return -1.

Requirements

To solve the problem, the following requirements must be met:

The array is sorted.
The elements in the array may not be distinct.
Negative values are allowed in the array.
If there is no magic index, return -1.

Example Usage

The following examples illustrate the usage of the function:

None input -> -1
Empty array -> -1

a[i]  -4 -2  2  6  6  6  6 10
  i    0  1  2  3  4  5  6  7

Result: 2

a[i]  -4 -2  1  6  6  6  6 10
  i    0  1  2  3  4  5  6  7

Result: 6

a[i]  -4 -2  1  6  6  6  7 10
  i    0  1  2  3  4  5  6  7

Result: -1

Summary

In summary, the magic index problem involves finding an element in a sorted array such that its value is equal to its index. The function must return the left-most magic index if there are multiple ones, and -1 if there is no magic index. The requirements for the function include a sorted array, the possibility of duplicate elements, and the allowance of negative values.

Identifying Magic Indexes in Arrays